A two-phase algorithm for bin stretching with stretching factor 1.5
From MaRDI portal
Abstract: Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.
Recommendations
- An efficient algorithm for bin stretching
- Bin stretching with migration on two hierarchical machines
- Better Algorithms for Online Bin Stretching
- scientific article; zbMATH DE number 2086931
- Improved approximation algorithm for two-dimensional bin packing
- A 13/12 approximation algorithm for bin packing with extendable bins
- Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
- scientific article; zbMATH DE number 1688388
- An improved approximation scheme for variable-sized bin packing
- An improved approximation scheme for variable-sized bin packing
Cites work
- An efficient algorithm for bin stretching
- Better Algorithms for Online Bin Stretching
- Bounds on Multiprocessing Timing Anomalies
- Improved lower bounds for the online bin stretching problem
- On-Line Load Balancing for Related Machines
- On-line bin-stretching
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- Online bin stretching with bunch techniques
- Online bin stretching with three bins
- Preemptive online scheduling: Optimal algorithms for all speeds
- Semi on-line algorithms for the partition problem
- Semi-online scheduling revisited
Cited in
(11)- On-line bin-stretching
- Tight upper bounds for semi-online scheduling on two uniform machines with known optimum
- A survey on makespan minimization in semi-online environments
- Online bin stretching with three bins
- An efficient algorithm for bin stretching
- An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time
- Bin stretching with migration on two hierarchical machines
- Tight lower bounds for semi-online scheduling on two uniform machines with known optimum
- Semi-online scheduling: a survey
- Bin stretching revisited
- Better algorithms for online bin stretching via computer search
This page was built for publication: A two-phase algorithm for bin stretching with stretching factor 1.5
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1680492)
