Tight approximation guarantees for concave coverage problems

DOI10.4230/LIPICS.STACS.2021.9MaRDI QIDQ7231532zbMATH OpenFDO

Authors Siddharth Barman, Omar Fawzi, Paul Fermé

Publication date 21 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2021.9

zbMATH Keywords

approximation algorithmsconcave functioncoverage problems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A threshold of ln n for approximating set cover
• Algorithmic Aspects of Optimal Channel Coding
• Algorithmic Game Theory
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Finding a collective set of items: from proportional multirepresentation to group recommendation
• Handbook of Computational Social Choice
• scientific article; zbMATH DE number 1894376 (Why is no real title available?)
• Limitations of randomized mechanisms for combinatorial auctions
• Maximizing a monotone submodular function subject to a matroid constraint
• Optimal approximation for submodular and supermodular optimization with bounded curvature
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Stochastic orders
• 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

This page was built for publication: Tight approximation guarantees for concave coverage problems

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