Structured Robust Submodular Maximization: Offline and Online Algorithms
Structured Robust Submodular Maximization: Offline and Online Algorithms
复制标题
DOI：
10.1287/ijoc.2020.0998
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Nima Anari;Nika Haghtalab;J. Naor;S. Pokutta;Mohit Singh;Alfredo Torrico
中科院分区：
文献类型：
--
作者：
Nima Anari;Nika Haghtalab;J. Naor;S. Pokutta;Mohit Singh;Alfredo Torrico
受约束的下函数最大化已用于子集选择问题，例如选择最有用的传感器位置。尽管这些模型非常受欢迎，但通过这种方法获得的解决方案对于定义了子模块功能的数据的扰动不稳定。鲁棒性的最大化已被提出为一个更丰富的模型，旨在克服这一差异并增加了下义优化的建模范围。在这项工作中，我们考虑使用结构化的组合约束来考虑强大的下二次最大化，并具有可证明的保证的有效算法。我们的方法适用于由单个或多个矩形和背包定义的约束以及分布鲁棒的标准。我们考虑了提前已知问题的数据定义问题的离线设置，也可以考虑随着时间的推移揭示输入数据的在线设置。对于离线设置，我们给出了一种一般（几乎）最佳双晶格近似算法，该算法依赖于经典算法的新扩展来实现supporular最大化。对于该问题的在线版本，我们给出了一种算法，该算法返回具有sublinear遗憾的双晶型解决方案。贡献的摘要：受限的下二次最大化是联合优化的核心领域之一，以及在操作研究和计算机科学中的各种应用。在过去的几十年中，两个社区都对具有可证明保证的新算法的设计和分析感兴趣。传感器位置，影响最大化和数据摘要是在上述社区交集处的下义优化的某些应用。特别是，我们的工作重点是同时优化几个子解体功能。我们为问题的离线和在线变体提供了新的见解和算法，从而大大扩展了相关文献。同时，我们提供了一项计算研究，以支持我们的理论结果。
Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. Although these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids and knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem are known in advance and the online setting where the input data are revealed over time. For the offline setting, we give a general (nearly) optimal bicriteria approximation algorithm that relies on new extensions of classical algorithms for submodular maximization. For the online version of the problem, we give an algorithm that returns a bicriteria solution with sublinear regret. Summary of Contribution: Constrained submodular maximization is one of the core areas in combinatorial optimization with a wide variety of applications in operations research and computer science. Over the last decades, both communities have been interested on the design and analysis of new algorithms with provable guarantees. Sensor location, influence maximization and data summarization are some of the applications of submodular optimization that lie at the intersection of the aforementioned communities. Particularly, our work focuses on optimizing several submodular functions simultaneously. We provide new insights and algorithms to the offline and online variants of the problem which significantly expand the related literature. At the same time, we provide a computational study that supports our theoretical results.