A robust APTAS for the classical bin packing problem

DOI10.1007/s10107-007-0200-yzbMath1163.90018OpenAlexW1988227873MaRDI QIDQ1013966

Asaf Levin, Leah Epstein

Publication date: 24 April 2009

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-007-0200-y

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (21)

Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Semi-on-line bin packing: a short overview and a new lower bound ⋮ Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ⋮ Online load balancing with general reassignment cost ⋮ Bin stretching with migration on two hierarchical machines ⋮ Online load balancing on uniform machines with limited migration ⋮ Unnamed Item ⋮ Online minimization of the maximum starting time: migration helps ⋮ Online bin covering with limited migration ⋮ Unnamed Item ⋮ Robust algorithms for preemptive scheduling ⋮ On-line machine covering on two machines with local migration ⋮ Fully-Dynamic Bin Packing with Little Repacking ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Robust algorithms for total completion time ⋮ Fully dynamic bin packing revisited ⋮ Online Bin Covering with Limited Migration ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ A Robust AFPTAS for Online Bin Packing with Polynomial Migration ⋮ Online scheduling with migration on two hierarchical machines ⋮ Robust online algorithms for dynamic choosing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time
• Bin packing can be solved within 1+epsilon in linear time
• An improved lower bound for on-line bin packing algorithms
• Repacking helps in bounded space on-line bin-packing
• Algorithms for the Relaxed Online Bin-Packing Model
• On the online bin packing problem
• A simple on-line bin-packing algorithm
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• Automata, Languages and Programming
• Toeplitz Matrices Associated with a Semi-Infinite Laurent Series

This page was built for publication: A robust APTAS for the classical bin packing problem