Stability and Recovery for Independence Systems
Stability and Recovery for Independence Systems
复制标题
独立系统的稳定性和恢复
DOI：
10.4230/lipics.esa.2017.26
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J. Vondrák
中科院分区：
文献类型：
--
作者：
Vaggos Chatziafratis;Tim Roughgarden;J. Vondrák
有两种类型的算法经常被报道在“真实世界”的实例中比在最坏的情况下表现得更好，这两种算法是贪婪算法和局部搜索算法。本文系统地研究了下闭可行约束下极大化单调子模集函数问题的这两类算法。我们认为扰动稳定的情况下，在这个意义上的Bilu和Linial，并精确地确定的稳定阈值，超过这些算法保证恢复最优解。我们的工作的副产品包括第一个定义的扰动稳定性的非添加剂的目标函数，和解决的最坏情况下的局部搜索的近似保证p-可扩展系统。
Two genres of heuristics that are frequently reported to perform much better on "real-world" instances than in the worst case are greedy algorithms and local search algorithms. In this paper, we systematically study these two types of algorithms for the problem of maximizing a monotone submodular set function subject to downward-closed feasibility constraints. We consider perturbation-stable instances, in the sense of Bilu and Linial, and precisely identify the stability threshold beyond which these algorithms are guaranteed to recover the optimal solution. Byproducts of our work include the first definition of perturbation-stability for non-additive objective functions, and a resolution of the worst-case approximation guarantee of local search in p-extendible systems.