Tight approximation bounds for maximum multi-coverage
From MaRDI portal
Publication:2118140
DOI10.1007/s10107-021-01677-4OpenAlexW3184864859MaRDI QIDQ2118140
Emirhan Gürpınar, Omar Fawzi, Siddharth Barman, Suprovat Ghoshal
Publication date: 22 March 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.00640
Related Items (3)
Siting renewable power generation assets with combinatorial optimisation ⋮ Tight Approximation Bounds for Maximum Multi-coverage ⋮ On the correlation gap of matroids
Cites Work
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Stochastic orders
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
- Approximation algorithms for combinatorial problems
- Negative association of random variables, with applications
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- A threshold of ln n for approximating set cover
- The Projection Games Conjecture and the NP-Hardness of ln n-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
- 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
- Bi-Covering: Covering Edges with Two Small Subsets of Vertices
- Balls and bins: A study in negative dependence
- Agnostic Learning of Monomials by Halfspaces Is Hard
- On Maximizing Welfare When Utility Functions Are Subadditive
- Channel Coding Rate in the Finite Blocklength Regime
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Limitations of Randomized Mechanisms for Combinatorial Auctions
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: Tight approximation bounds for maximum multi-coverage
