Set Covering with Ordered Replacement: Additive and Multiplicative Gaps
From MaRDI portal
Publication:3009761
DOI10.1007/978-3-642-20807-2_14zbMath1341.90108arXiv1012.3295OpenAlexW1653177996MaRDI QIDQ3009761
Thomas Rothvoß, Laura Sanità, Friedrich Eisenbrand, Naonori Kakimura
Publication date: 24 June 2011
Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.3295
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Combinatorial aspects of packing and covering (05B40)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- There is no asymptotic PTAS for two-dimensional vector packing
- Asymptotic fully polynomial approximation schemes for variants of open-end bin packing
- Asymptotics of the chromatic index for multigraphs
- Bin packing can be solved within 1+epsilon in linear time
- On the ratio of optimal integral and fractional covers
- A sublinear bound on the chromatic index of multigraphs
- Bin packing with general cost structures
- Bin Packing via Discrepancy of Permutations
- The Train Delivery Problem - Vehicle Routing Meets Bin Packing
- AFPTAS Results for Common Variants of Bin Packing: A New Method for Handling the Small Items
- A threshold of ln n for approximating set cover
- An APTAS for Generalized Cost Variable-Sized Bin Packing
- A Greedy Heuristic for the Set-Covering Problem
- Approximation schemes for ordered vector packing problems
- Probability and Computing
This page was built for publication: Set Covering with Ordered Replacement: Additive and Multiplicative Gaps