Repacking helps in bounded space on-line bin-packing

DOI10.1007/BF02248693zbMath0772.90052OpenAlexW1825427184MaRDI QIDQ1207048

Gerhard J. Woeginger, Gábor Galambos

Publication date: 4 May 1993

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02248693

zbMATH Keywords

polynomial time approximation algorithmsuboptimal algorithmsrepackingon-line bounded-space bin-packing

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (20)

Online Bin Packing with Advice of Small Size ⋮ Semi-on-line bin packing: a short overview and a new lower bound ⋮ Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems ⋮ Homogeneous grouping of non-prime steel products for online auctions: a case study ⋮ On-line bin packing ? A restricted survey ⋮ A 4-space bounded approximation algorithm for online bin packing problem ⋮ Tight bounds for NF-based bounded-space online bin packing algorithms ⋮ On-line bin packing with restricted repacking ⋮ Quality of equilibria for selfish bin packing with cost sharing variants ⋮ On bin packing with clustering and bin packing with delays ⋮ Resource augmented semi-online bounded space bin packing ⋮ Batched bin packing ⋮ More on batched bin packing ⋮ A robust APTAS for the classical bin packing problem ⋮ Improved lower bounds for semi-online bin packing problems ⋮ Quality of strong equilibria for selfish bin packing with uniform cost sharing ⋮ Online bin packing with advice of small size ⋮ NF-Based Algorithms for Online Bin Packing with Buffer and Item Size Limitation ⋮ NF-based algorithms for online bin packing with buffer and bounded item size ⋮ Online bin packing with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Resource constrained scheduling as generalized bin packing
• Fast algorithms for bin packing
• A simple on-line bin-packing algorithm
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Improved Space for Bounded-Space, On-Line Bin-Packing
• On Certain Nonlinear Recurring Sequences

This page was built for publication: Repacking helps in bounded space on-line bin-packing