Tight Approximation Bounds for Maximum Multi-coverage
From MaRDI portal
Publication:5041735
DOI10.1007/978-3-030-45771-6_6zbMath1503.90104OpenAlexW3021188966MaRDI QIDQ5041735
Omar Fawzi, Siddharth Barman, Suprovat Ghoshal, Emirhan Gürpınar
Publication date: 14 October 2022
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-45771-6_6
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Parameterized complexity of \(d\)-hitting set with quotas, A simple optimal contention resolution scheme for uniform matroids
Cites Work
- Unnamed Item
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
- Approximation algorithms for combinatorial problems
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Tight approximation bounds for maximum multi-coverage
- On the set multicover problem in geometric settings
- A threshold of ln n for approximating set cover
- Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- On the power of unique 2-prover 1-round games
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Exact Algorithms for Set Multicover and Multiset Multicover Problems
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- Algorithmic Aspects of Optimal Channel Coding
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- On Maximizing Welfare When Utility Functions Are Subadditive
- Channel Coding Rate in the Finite Blocklength Regime
- Limitations of Randomized Mechanisms for Combinatorial Auctions
