Online multiset submodular cover

DOI10.1007/s00453-024-01234-3MaRDI QIDQ6582377

Dror Rawitz, Magnús M. Halldórsson

Publication date: 2 August 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

competitive analysisteam formationcapacitated coveringonline multiset multicoversubmodular coverage

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Shrinking maxima, decreasing costs: new online packing and covering problems
• Randomized approximation of bounded multicovering problems
• A fast approximation algorithm for the multicovering problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithms for covering/packing integer programs
• An improved approximation algorithm for vertex cover with hard capacities
• Algorithmic construction of sets for k -restrictions
• Tight Approximation Bounds for the Seminar Assignment Problem
• A threshold of ln n for approximating set cover
• Online Primal-Dual Algorithms for Covering and Packing
• Covering Problems with Hard Capacities
• The Online Set Cover Problem
• The importance of being biased
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• On the hardness of approximating minimization problems
• Capacitated vertex covering
• The Online Submodular Cover Problem
• Analytical approach to parallel repetition
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

This page was built for publication: Online multiset submodular cover