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

DOI10.1016/S0020-0190(97)00216-0zbMATH Open1338.68291MaRDI QIDQ293250FDOQ293250

Authors: Paolo Dell'Olmo, Hans Kellerer, Zsolt Tuza, 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

Recommendations

• Approximation algorithms for extensible bin packing
• Approximation algorithms for extensible bin packing
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 5761817
• Approximation schemes for the generalized extensible bin packing problem

zbMATH Keywords

approximation algorithmsschedulingbin packingworst-case performance

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Bounds on Multiprocessing Timing Anomalies
• Title not available (Why is that?)
• On-line approximation algorithms for scheduling tasks on identical machines with extendable working time

Cited In (18)

• State-Variable Modeling for a Class of Two-Stage Stochastic Optimization Problems
• 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 extensible bin packing
• Approximation algorithms for partitioning small items in unequal bins to minimize the total size
• Branch and Price for Chance-Constrained Bin Packing
• A two-phase algorithm for bin stretching with stretching factor 1.5
• Scheduling jobs with normally distributed processing times on parallel machines
• Adaptive Bin Packing with Overflow
• Robust allocation of operating rooms: a cutting plane approach to handle lognormal case durations
• Improved bounds for stochastic extensible bin packing under distributional assumptions
• Applying extra-resource analysis to load balancing.
• Approximation and Online Algorithms
• Fast approximation methods for online scheduling of outpatient procedure centers
• Vector assignment schemes for asymmetric settings
• Optimal preemptive scheduling for general target functions

This page was built for publication: A 13/12 approximation algorithm for bin packing with extendable bins

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