Bài toán Submodular Cover là một trong những phần quan trọng của toán tối ưu và thuật toán xấp xỉ. Nó được ứng dụng đa dạng trong học máy, khoa học máy tính, tiếp thị số và kinh tế. Bài viết trình bày nghiên cứu và đề xuất thuật toán Streaming để giải quyết cho bài toán Submodular cover trong môi trường nhiễu cộng (Streaming Submodular Cover under Additive Noise - SSCAN). | Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR TP. HCM ngày 23-24 12 2021 DOI GIẢI QUYẾT BÀI TOÁN SUBMODULAR COVER TRONG MÔI TRƯỜNG NHIỄU CỘNG BẰNG THUẬT TOÁN STREAMING Nguyễn Thị Bích Ngân Trần Hữu Lợi Nguyễn Đình Thìn Phạm Nguyễn Huy Phương Đại học Công nghiệp Thực phẩm TP. Hồ Chí Minh nganntb@ tranloi876@ nguyendinhthinkg@ phuongpnh@ TÓM TẮT Bài toán Submodular Cover là một trong những phần quan trọng của toán tối ưu và thuật toán xấp xỉ. Nó được ứng dụng đa dạng trong học máy khoa học máy tính tiếp thị số và kinh tế. Các nghiên cứu trước đây tập trung giải quyết bài toán trong môi trường không có nhiễu hoặc áp dụng thuật toán tham lam để giải quyết với môi trường có nhiễu. Tuy nhiên dữ liệu thực tế của một số ứng dụng thường có quy mô rất lớn do đó việc xuất hiện nhiễu trong dữ liệu là điều không tránh khỏi. Nguyên nhân này làm giảm tính hiệu quả của các phương pháp được đề xuất trước đây hoặc không khả thi khi đưa vào ứng dụng. Dựa trên ý tưởng đó trong bài báo này chúng tôi nghiên cứu và đề xuất thuật toán Streaming để giải quyết cho bài toán Submodular cover trong môi trường nhiễu cộng Streaming Submodular Cover under Additive Noise - SSCAN . Phương pháp mà chúng tôi đề xuất sẽ duyệt một lần qua bộ dữ liệu single-pass streaming trong khi vẫn đảm bảo kết quả có độ chính xác xấp xỉ tiệm cận kết quả tối ưu. Kết quả thực nghiệm cho thấy thuật toán SSCAN đạt kết quả cao với hàm mục tiêu objective function và có hiệu suất vượt trội so với các thuật toán tham lam hiện tại cả về số lần truy vấn hàm mục tiêu và thời gian thực thi chương trình. Từ khóa Submodular Cover thuật toán xấp xỉ nhiễu cộng thuật toán Streaming. I. GIỚI THIỆU Việc tối ưu hóa các hàm submodular là một bài toán quan trọng trong nhiều lĩnh vực đã được chứng minh qua các nghiên cứu khoa học. Nó xuất hiện rộng rãi trong nhiều ứng dụng như kinh tế 1 phúc lợi xã hội 21 tối ưu hóa tổ .
