Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	张宏扬，宁波大学
Inviter:
Title:	Streaming algorithm for submodular cover problem
Time & Venue:	2022.11.13 19:00-20:00 腾讯会议 ID：644-493-021
Abstract:	In this work, we mainly investigate the problem that minimizes the price function such that the valuation function exceeds a required threshold in submodular cover problem, where the price function is additive, and the valuation function is submodular. We study the problem under streaming model and propose bicriteria approximation algorithms. We find when the valuation function is no less than a threshold, the price function is no more than some bound κ. We also provide numerical experiments to measure the performance of our algorithm.