Một số thuật toán xấp xỉ cho bài toán tối ưu hàm dạng submodular với ràng buộc

Tóm tắt

Luận án chọn chủ đề nghiên cứu: “Một số thuật toán xấp xỉ cho bài toán tối ưu hàm dạng submodular với ràng buộc”. Trong đó, do tính độc đáo, giá trị thực tiễn lớn của ba bài toán đã nêu, cùng với các thách thức của chúng, luận án đặt vấn đề nghiên cứu các thuật toán xấp xỉ để giải quyết các bài toán này. Trong đó, mục tiêu chung là các thuật toán xấp xỉ phải hiệu quả với tỉ lệ xấp xỉ cạnh tranh và giảm độ phức tạp truy vấn. Mục tiêu cụ thể như sau: 1. Nghiên cứu bài toán 1 - kSMK với các mục tiêu: - Đề xuất thuật toán xấp xỉ giải quyết bài toán kSMK. Thuật toán đưa ra cho tỉ lệ xấp xỉ cạnh tranh với các thuật toán cho tỉ lệ xấp xỉ tốt nhất hiện nay. Đồng thời, giảm độ phức tạp truy vấn xuống còn tuyến tính; - Giải bài toán khi hàm mục tiêu không còn đơn điệu; 2. Nghiên cứu bài toán 2 - SMKN với các mục tiêu: - Xây dựng mô hình bài toán tối đa hàm submodular với ràng buộc chi phí dưới sự tác động của 2 loại nhiễu: nhiễu cộng và nhiễu nhân; - Đề xuất thuật toán tham lam giải quyết bài toán; - Đề xuất thuật toán luồng cải tiến phương pháp tham lam. 3. Nghiên cứu bài toán 3 - DRSC với các mục tiêu: - Nghiên cứu tính chất DR-submodular và mô hình hóa bài toán DRSC; - Đề xuất thuật toán xấp xỉ hiệu quả giải quyết bài toán DRSC. Với bài toán này, hướng thuật toán đề xuất dựa trên thiết kế song song với độ phức tạp truy vấn và độ phức tạp song song thấp.