Stability and recovery for independence systems

DOI10.4230/LIPICS.ESA.2017.26zbMATH Open1442.68263arXiv1705.00127OpenAlexW2963605961MaRDI QIDQ5111712FDOQ5111712

Authors: Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák 

Publication date: 27 May 2020

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.

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

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

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Robust independence systems
• Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry
• A new approximation guarantee for monotone submodular function maximization via discrete convexity
• Title not available (Why is that?)

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)