Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.ESA.2017.26 | european symposium on algorithms |
DocType | Volume | Issue |
Conference | abs/1705.00127 | 87 |
Citations | PageRank | References |
2 | 0.38 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vaggos Chatziafratis | 1 | 9 | 4.23 |
| Tim Roughgarden | 2 | 4177 | 353.32 |
| Jan Vondrák | 3 | 888 | 47.94 |