Shrinking maxima, decreasing costs: new online packing and covering problems
DOI10.1007/S00453-015-9995-8zbMATH Open1339.68319OpenAlexW2001148478MaRDI QIDQ289907FDOQ289907
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
Recommendations
randomized algorithmcompetitive analysisonline set packingpacking integer programsprize-collecting multi-coveringteam formation
Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Combinatorial optimization (90C27) Integer programming (90C10)
Cites Work
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Online Primal-Dual Algorithms for Covering and Packing
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Independent sets with domination constraints
- Competitive router scheduling with structured data
- On the complexity of approximating \(k\)-set packing
- A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
- Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
- Online Set 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
- Online scheduling with interval conflicts
- Approximate Algorithms for the 0/1 Knapsack Problem
- Title not available (Why is that?)
- On Multidimensional Packing Problems
- Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
Cited In (4)
This page was built for publication: Shrinking maxima, decreasing costs: new online packing and covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q289907)
