09/11/2023: Hà Thị Kim Dung (Học viện An ninh nhân dân) Thuật toán xấp xỉ cho bài toán Tối đa hàm -submodular không đơn điệu với ràng buộc chi phí

Bài toán kSMK là một bài toán tối ưu tổ hợp phổ biến với hàm mục tiêu có dạng k-submodular được áp dụng trong nhiều ứng dụng cụ thể như: Tối đa ảnh hưởng của k chủ đề, đặt k loại sensor cảm biến, …. kSMK mở rộng bài toán Tối đa hàm tập hợp submodular và là bài toán NP-khó nên khó tính toán chính xác lời giải trong thời gian đa thức. Các thuật toán xấp xỉ hiện nay gặp vấn đề lớn với thời gian chạy khi tập dữ liệu đầu vào V tăng lên về kích cỡ, và số lần gọi hàm mục tiêu. Bài trình bày đưa ra 2 thuật toán tất định với số lượng truy vấn lời gọi hàm mục tiêu là tuyến tính. Kết quả của 2 thuật toán đưa ra ý nghĩa khi các đảm bảo lý thuyết được duy trì về tỉ lệ xấp xỉ, nhưng vẫn giảm được độ phức tạp truy vấn, qua đó góp phần giảm được vấn đề thời gian chạy.

Speaker: Hà Thị Kim Dung, Học viện An ninh nhân dân

Time: 14:00, Thursday, November 09, 2023

Venue: Room 405 E3

Hà Thị Kim Dung hiện đang công tác tại Học viện An ninh nhân dân, là NCS K27 KHMT (QH 2020) của Bộ môn Khoa học máy tính, Khoa CNTT, Đại học Công nghệ, ĐHQG Hà nội. NCS đang trong quá trình hoàn thiện luận án để gửi phản biện kín cấp ĐHQG.

Xê-mi-na khoa học định kỳ được Bộ môn Khoa học máy tính – Khoa Công nghệ thông tin, Viện Trí tuệ nhân tạo, và Viện Tiên tiến về Kỹ thuật và Công nghệ phối hợp thực hiện.