Shrinking maxima, decreasing costs: new online packing and covering problems
From MaRDI portal
Publication:289907
DOI10.1007/s00453-015-9995-8zbMath1339.68319OpenAlexW2001148478MaRDI QIDQ289907
Boaz Patt-Shamir, Magnús M. Halldórsson, Pierre Fraigniaud, Adi Rosén, Dror Rawitz
Publication date: 31 May 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-9995-8
competitive analysisrandomized algorithmonline set packingpacking integer programsprize-collecting multi-coveringteam formation
Integer programming (90C10) Combinatorial optimization (90C27) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (3)
Distributed Testing of Distance-k Colorings ⋮ Overflow management with self-eliminations ⋮ Overflow management with self-eliminations
Cites Work
- Unnamed Item
- Unnamed Item
- Online scheduling with interval conflicts
- Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Independent sets with domination constraints
- Competitive router scheduling with structured data
- On the complexity of approximating \(k\)-set packing
- Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
- Online Set Packing
- Online Primal-Dual Algorithms for Covering and Packing
- The Online Set Cover Problem
- Submodular Secretary Problem and Extensions
- The Secretary Problem and Its Extensions: A Review
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Approximate Algorithms for the 0/1 Knapsack Problem
- On Multidimensional Packing Problems
This page was built for publication: Shrinking maxima, decreasing costs: new online packing and covering problems
