Robust monotone submodular function maximization

• 成果类型: Article
• 署名作者: Orlin, James B.; Schulz, Andreas S.; Udwani, Rajan
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1320-2
• 发表日期: 2018
• 页码: 505-537
• 关键词: function subject; optimization; constraint; algorithm; selection

摘要

We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42: 427- 486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w. r. t. adversarial removal of up to t elements from the chosen set. For the fundamental case of t = 1, we give a deterministic (1 - 1/e) - 1/T(m) approximation algorithm, where m is an input parameter and number of queries scale as O(nm+ 1). In the process, we develop a deterministic (1 - 1/e) - 1/T(m) approximate greedy algorithm for bi- objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (in: FOCS 10, IEEE, pp 575- 584, 2010), we show a randomized (1 - 1/e) - approximation for constant t and = 1 O(t), making O(n1/ 3) queries. Further, for t v k, we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robustmaximization subject to an Independence System.