Nov 28, 2022
Speaker · 0 followers
Speaker · 0 followers
Speaker · 0 followers
The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by Hassidim and Singer (2017). For a cardinality constraint, we propose an algorithm achieving a near-optimal (1-1/e-O(epsilon))-approximation guarantee (for arbitrary epsilon > 0) with only a polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of Singer and Hassidim (2018). For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design a novel local search framework that can handle the effect of noise and to construct certain smoothing surrogate functions for noise reduction.The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by Hassidim and Singer (2017). For a cardinality constraint, we propose an algorithm achieving …
Account · 962 followers
Professional recording and live streaming, delivered globally.
Presentations on similar topic, category or speaker
Conglong Li, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Junyu Xie, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Tim Pearce, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Junwen Yang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Xiaojun Xu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%