A 13/12 approximation algorithm for bin packing with extendable bins

DOI10.1016/S0020-0190(97)00216-0zbMath1338.68291MaRDI QIDQ293250

Hans Kellerer, Zsolt Tuza, Paolo Dell'Olmo, Maria Grazia Speranza

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002160?np=y

zbMATH Keywords

schedulingworst-case performanceapproximation algorithmsbin packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items

Approximation schemes for the generalized extensible bin packing problem, State-Variable Modeling for a Class of Two-Stage Stochastic Optimization Problems, Approximation algorithms for extensible bin packing, Improved bounds for stochastic extensible bin packing under distributional assumptions, Fast Approximation Methods for Online Scheduling of Outpatient Procedure Centers, Combinatorial optimization problems in wireless switch design, Scheduling jobs with normally distributed processing times on parallel machines, Vector assignment schemes for asymmetric settings, Robust allocation of operating rooms: a cutting plane approach to handle lognormal case durations, On-line scheduling with extendable working time on a small number of machines, Branch and Price for Chance-Constrained Bin Packing, Approximation algorithms for partitioning small items in unequal bins to minimize the total size, Applying extra-resource analysis to load balancing., Optimal preemptive scheduling for general target functions, Adaptive Bin Packing with Overflow

Cites Work

• On-line approximation algorithms for scheduling tasks on identical machines with extendable working time
• Bounds on Multiprocessing Timing Anomalies
• Unnamed Item
• Unnamed Item