Improved Approximations for k-Exchange Systems

DOI10.1007/978-3-642-23719-5_66zbMath1246.68263OpenAlexW1883792619MaRDI QIDQ3092280

Joseph (Seffi) Naor, Moran Feldman, Justin Ward, Roy Schwartz

Publication date: 16 September 2011

Published in: Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-23719-5_66

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (14)

Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ A multi-pass streaming algorithm for regularized submodular maximization ⋮ The Power of Subsampling in Submodular Maximization ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ Practical budgeted submodular maximization ⋮ A constrained two-stage submodular maximization ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ On the intersection of independence systems ⋮ Two-stage submodular maximization under curvature ⋮ Unnamed Item ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

This page was built for publication: Improved Approximations for k-Exchange Systems