Stability and recovery for independence systems

DOI10.4230/LIPICS.ESA.2017.26MaRDI QIDQ5111712zbMATH OpenOpenAlexFDO

Authors Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1705.00127

zbMATH Keywords

stabilityapproximation algorithmsgreedy algorithmslocal search algorithmssubmodular functions\(p\)-systems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

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, 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.

Recommendations

• Fast algorithms for maximizing submodular functions
• Maximizing Non-monotone Submodular Functions
• Robust monotone submodular function maximization
• Monotone submodular maximization over a matroid via non-oblivious local search
• Techniques for submodular maximization

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 5485445 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• scientific article; zbMATH DE number 1973378 (Why is no real title available?)
• Algorithms for stable and perturbation-resilient problems
• An Analysis of the Greedy Heuristic for Independence Systems
• An analysis of approximations for maximizing submodular set functions—I
• Approximating the \(k\)-set packing problem by local improvements
• Are stable instances easy?
• Center-based clustering under perturbation stability
• Clustering under approximation stability
• Combinatorial auctions with decreasing marginal utilities
• Computationally feasible VCG mechanisms
• Constant factor approximation for balanced cut in the PIE model
• Data stability in clustering: a closer look
• Effectiveness of local search for geometric optimization
• Evolutionary algorithms and matroid optimization problems
• Greedy in Approximation Algorithms
• Large neighborhood local search for the maximum set packing problem
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Maximizing a monotone submodular function subject to a matroid constraint
• Nash equilibria in perturbation-stable games
• Networks, crowds and markets. Reasoning about a highly connected world.
• On the Complexity of the Metric TSP under Stability Considerations
• On the practically interesting instances of MAXCUT
• Optimal approximation for the submodular welfare problem in the value oracle model
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• The power of local search: maximum coverage over a matroid
• Traveling salesman problem heuristics: leading methods, implementations and latest advances
• \(k\)-center clustering under perturbation resilience

Cited in

(4)

• A new approximation guarantee for monotone submodular function maximization via discrete convexity
• Bilu-Linial stability, certified algorithms and the independent set problem
• Robust independence systems
• scientific article; zbMATH DE number 2226685 (Why is no real title available?)

This page was built for publication: Stability and recovery for independence systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111712)