Tight approximation bounds for maximum multi-coverage

DOI10.1007/978-3-030-45771-6_6MaRDI QIDQ5041735zbMATH OpenOpenAlexFDO

Authors Siddharth Barman, Omar Fawzi, 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

zbMATH Keywords

approximation algorithmscovering problemssubmodular optimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1323125
• Approximation algorithm for the partial set multi-cover problem
• The budgeted maximum coverage problem
• Approximation algorithm for the multicovering problem
• Algorithms for covering multiple submodular constraints and applications

Cites work

• scientific article; zbMATH DE number 605729 (Why is no real title available?)
• 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
• Channel Coding Rate in the Finite Blocklength Regime
• Exact algorithms for set multicover and multiset multicover problems
• 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
• On maximizing welfare when utility functions are subadditive
• On the power of unique 2-prover 1-round games
• On the set multicover problem in geometric settings
• 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
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Tight approximation bounds for maximum multi-coverage
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited in

(8)

• The generalized maximum coverage problem
• Parameterized complexity of d-hitting set with quotas
• Randomized approximation of bounded multicovering problems
• Tight bounds for double coverage against weak adversaries
• Tight approximation bounds for maximum multi-coverage
• Tight Bounds for Double Coverage Against Weak Adversaries
• Tight approximation bounds for combinatorial frugal coverage algorithms
• A simple optimal contention resolution scheme for uniform 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 Q5041735)