Online budgeted maximum coverage

DOI10.1007/s00453-021-00850-7OpenAlexW3179437496MaRDI QIDQ1979466

Dror Rawitz, Adi Rosén

Publication date: 2 September 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6414/

zbMATH Keywords

competitive analysisonline algorithmsmaximum coveragebudgeted coverageremovable online knapsack

Mathematics Subject Classification ID

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

Related Items

Online algorithms for the maximum \(k\)-interval coverage problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online knapsack revisited
• Online maximum \(k\)-coverage
• Randomized algorithms for online knapsack problems
• Submodular maximization meets streaming: matchings, matroids, and more
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• On-line vertex-covering
• Stochastic on-line knapsack problems
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• On the Advice Complexity of the Set Cover Problem
• Algorithmic construction of sets for k -restrictions
• Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
• A threshold of ln n for approximating set cover
• Online Primal-Dual Algorithms for Covering and Packing
• The Online Set Cover Problem
• The importance of being biased
• The Maximum Coverage Location Problem
• 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
• Optimal Location of Discretionary Service Facilities
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• An analysis of approximations for maximizing submodular set functions—I
• Online Budgeted Maximum Coverage
• Locating Discretionary Service Facilities, II: Maximizing Market Size, Minimizing Inconvenience
• Online Submodular Maximization with Preemption
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Submodular Maximization with Cardinality Constraints