Repacking helps in bounded space on-line bin-packing

DOI10.1007/BF02248693MaRDI QIDQ1207048zbMATH OpenOpenAlexFDO

Authors Gábor Galambos, Gerhard J. Woeginger

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

on-line bounded-space bin-packingpolynomial time approximation algorithmrepackingsuboptimal algorithms

Mathematics Subject Classification ID

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

Recommendations

• Resource augmented semi-online bounded space bin packing
• Two-bounded-space bin packing revisited
• scientific article; zbMATH DE number 1134660
• Improved Space for Bounded-Space, On-Line Bin-Packing
• Resource augmentation for online bounded space bin packing

Cites work

• A simple on-line bin-packing algorithm
• Fast algorithms for bin packing
• scientific article; zbMATH DE number 432833 (Why is no real title available?)
• scientific article; zbMATH DE number 4125007 (Why is no real title available?)
• Improved Space for Bounded-Space, On-Line Bin-Packing
• On Certain Nonlinear Recurring Sequences
• Resource constrained scheduling as generalized bin packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(22)

• A robust APTAS for the classical bin packing problem
• Improved lower bounds for semi-online bin packing problems
• Tight bounds for NF-based bounded-space online bin packing algorithms
• Batched bin packing
• More on batched bin packing
• Homogeneous grouping of non-prime steel products for online auctions: a case study
• Quality of equilibria for selfish bin packing with cost sharing variants
• On bin packing with clustering and bin packing with delays
• 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 bounded item size
• Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
• On-line bin packing with restricted repacking
• Online bin packing with advice
• NF-based algorithms for online bin packing with buffer and item size limitation
• Semi-on-line bin packing: a short overview and a new lower bound
• Two-bounded-space bin packing revisited
• Online bin packing with advice of small size
• On-line bin packing ? A restricted survey
• Algorithms for the on-line bin packing problem with repacking
• A 4-space bounded approximation algorithm for online bin packing problem
• Resource augmented semi-online bounded space bin packing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1207048)