Stability and Recovery for Independence Systems
From MaRDI portal
Publication:5111712
DOI10.4230/LIPIcs.ESA.2017.26zbMath1442.68263arXiv1705.00127OpenAlexW2963605961MaRDI QIDQ5111712
Jan Vondrák, Vaggos Chatziafratis, Tim Roughgarden
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1705.00127
stabilityapproximation algorithmsgreedy algorithmslocal search algorithmssubmodular functions\(p\)-systems
Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)
Related Items (3)
Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- Traveling salesman problem heuristics: leading methods, implementations and latest advances
- Center-based clustering under perturbation stability
- Evolutionary algorithms and matroid optimization problems
- Combinatorial auctions with decreasing marginal utilities
- Are Stable Instances Easy?
- On the practically interesting instances of MAXCUT
- On the Complexity of the Metric TSP under Stability Considerations
- Data Stability in Clustering: A Closer Look
- Approximating the $$k$$-Set Packing Problem by Local Improvements
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- An analysis of approximations for maximizing submodular set functions—I
- An Analysis of the Greedy Heuristic for Independence Systems
- k-Center Clustering Under Perturbation Resilience
- Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
- Algorithms for stable and perturbation-resilient problems
- Constant factor approximation for balanced cut in the PIE model
- Large Neighborhood Local Search for the Maximum Set Packing Problem
- The effectiveness of lloyd-type methods for the k-means problem
- Clustering under approximation stability
- Greedy in Approximation Algorithms
- Clustering under Perturbation Resilience
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Stability and Recovery for Independence Systems
