Online budgeted maximum coverage

DOI10.1007/S00453-021-00850-7MaRDI QIDQ1979466zbMATH OpenOpenAlexFDO

Authors 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

budgeted coveragecompetitive analysismaximum coverageonline algorithmsremovable online knapsack

Mathematics Subject Classification ID

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

Recommendations

• Online budgeted maximum coverage
• The budgeted maximum coverage problem
• Randomized algorithms for online knapsack problems
• The online set cover problem
• The online set cover problem

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• Algorithmic construction of sets for k -restrictions
• An analysis of approximations for maximizing submodular set functions—I
• Approximate Algorithms for the 0/1 Knapsack Problem
• Approximation algorithms for combinatorial problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Buyback problem -- approximate matroid intersection with cancellation costs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256771 (Why is no real title available?)
• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2086630 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Locating Discretionary Service Facilities, II: Maximizing Market Size, Minimizing Inconvenience
• On the advice complexity of the set cover problem
• On the ratio of optimal integral and fractional covers
• On-line vertex-covering
• Online budgeted maximum coverage
• Online knapsack revisited
• Online maximum \(k\)-coverage
• Online primal-dual algorithms for covering and packing
• Online submodular maximization with preemption
• Optimal Location of Discretionary Service Facilities
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Randomized algorithms for online knapsack problems
• Stochastic on-line knapsack problems
• Submodular maximization with cardinality constraints
• The budgeted maximum coverage problem
• The importance of being biased
• The Maximum Coverage Location Problem
• The online set cover problem

Cited in

(2)

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

This page was built for publication: Online budgeted maximum coverage

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