A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing

DOI10.1137/080736831zbMath1201.90071OpenAlexW2117839333MaRDI QIDQ3586179

M. I. Sviridenko, Nikhil Bansal, Alberto Caprara

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/a-new-approximation-method-for-set-covering-problems-with-applications-to-multidimensional-bin-packing(06271704-8e96-4b17-93a8-1e29f1f5ce71).html

zbMATH Keywords

approximation algorithmbin packingset cover

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Related Items (21)

Choosing among heterogeneous server clouds ⋮ Packing anchored rectangles ⋮ Polynomial-time approximation schemes for circle and other packing problems ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A Service System with Packing Constraints: Greedy Randomized Algorithm Achieving Sublinear in Scale Optimality Gap ⋮ A \((5/3+\varepsilon)\)-approximation for strip packing ⋮ Tight approximation algorithms for geometric bin packing with skewed items ⋮ Peak demand minimization via sliced strip packing ⋮ There is no APTAS for 2-dimensional vector bin packing: revisited ⋮ Bin packing with general cost structures ⋮ Fractional Set Cover in the Streaming Model. ⋮ The minimum feasible tileset problem ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ Online square-into-square packing ⋮ TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING ⋮ Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints ⋮ Two-dimensional online bin packing with rotation ⋮ A set covering based approach to find the reduct of variable precision rough set ⋮ Large-scale heterogeneous service systems with general packing constraints ⋮ Approximation algorithms for orthogonal packing problems for hypercubes ⋮ New approximability results for two-dimensional bin packing

This page was built for publication: A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing