文章基本信息

标题：Stability and Recovery for Independence Systems
本地全文：下载
作者：Vaggos Chatziafratis ; Tim Roughgarden ; Jan Vondrak 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：26:1-26:15
DOI：10.4230/LIPIcs.ESA.2017.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 [11], 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.
关键词：Submodular; approximation; stability; Local Search; Greedy; p-systems