Tight approximation bounds for maximum multi-coverage

DOI10.1007/978-3-030-45771-6_6zbMATH Open1503.90104OpenAlexW3021188966MaRDI QIDQ5041735FDOQ5041735

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

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

zbMATH Keywords

approximation algorithmscovering problemssubmodular optimization

Mathematics Subject Classification ID

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

Cites Work

• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• Maximizing a monotone submodular function subject to a matroid constraint
• On the power of unique 2-prover 1-round games
• An analysis of approximations for maximizing submodular set functions—I
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Channel Coding Rate in the Finite Blocklength Regime
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Algorithmic Aspects of Optimal Channel Coding
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding
• On maximizing welfare when utility functions are subadditive
• Tight approximation bounds for maximum multi-coverage
• Exact algorithms for set multicover and multiset multicover problems
• Limitations of randomized mechanisms for combinatorial auctions
• On the set multicover problem in geometric settings

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)