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

68Q25: Analysis of algorithms and problem complexity

68W25: Approximation algorithms

Related Items

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

Cites Work

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