The ground-set-cost budgeted maximum coverage problem

DOI10.1007/S00224-025-10248-5MaRDI QIDQ6879182zbMATH OpenFDO

Authors Irving van Heuven van Staereling, Bart de Keijzer, Guido Schäfer

Publication date 2 January 2026

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-025-10248-5

zbMATH Keywords

approximation algorithmshypergraphsmaximum coverage problemsponsored searchsubmodular optimization

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites work

• A threshold of ln n for approximating set cover
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Detecting Feedback Vertex Sets of Size k in O ^⋆ (2.7 k ) Time
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Faster deterministic \textsc{Feedback Vertex Set}
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Maximizing a monotone submodular function subject to a matroid constraint
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• The budgeted maximum coverage problem
• The generalized maximum coverage problem

This page was built for publication: The ground-set-cost budgeted maximum coverage problem

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