Set Covering with Ordered Replacement: Additive and Multiplicative Gaps

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

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Combinatorial aspects of packing and covering (05B40)

Related Items (2)

A new integer programming formulation of the graphical traveling salesman problem ⋮ Unnamed Item

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