Tight approximation bounds for maximum multi-coverage

DOI10.1007/S10107-021-01677-4MaRDI QIDQ2118140zbMATH OpenOpenAlexFDO

Authors Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, Emirhan Gürpınar

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

zbMATH Keywords

approximation algorithmconvex ordermaximum coveragerandomized rounding

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Tight approximation bounds for maximum multi-coverage
• scientific article; zbMATH DE number 1323125
• The budgeted maximum coverage problem
• Algorithms for covering multiple submodular constraints and applications
• The power of local search: maximum coverage over a matroid

Cites work

• A threshold of ln n for approximating set cover
• Algorithmic Aspects of Optimal Channel Coding
• An analysis of approximations for maximizing submodular set functions—I
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Approximation algorithms for combinatorial problems
• Balls and bins: A study in negative dependence
• Bi-covering: covering edges with two small subsets of vertices
• Channel Coding Rate in the Finite Blocklength Regime
• Concentration of measure for the analysis of randomized algorithms.
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Limitations of randomized mechanisms for combinatorial auctions
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Negative association of random variables, with applications
• On maximizing welfare when utility functions are subadditive
• On the power of unique 2-prover 1-round games
• Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• Stochastic orders
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The projection games conjecture and the NP-hardness of n-approximating Set-Cover
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited in

(9)

• Tight bounds for double coverage against weak adversaries
• Siting renewable power generation assets with combinatorial optimisation
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Tight Bounds for Double Coverage Against Weak Adversaries
• Tight approximation bounds for maximum multi-coverage
• On the correlation gap of matroids
• Randomized approximation of bounded multicovering problems
• A 1/2-approximation algorithm for maximum interval multi-cover
• On the correlation gap of matroids

This page was built for publication: Tight approximation bounds for maximum multi-coverage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118140)