Online bin stretching with three bins

DOI10.1007/S10951-016-0504-YMaRDI QIDQ1702659zbMATH OpenOpenAlexFDO

Authors Martin Böhm, Jiří Sgall, Rob van Stee, Pavel Veselý

Publication date 28 February 2018

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5569

zbMATH Keywords

bin packingbin stretchinggame tree searchlower bounds for online algorithmsonline algorithmssemi-online algorithmssemi-online scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27) Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35)

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 $11/8=1.375$ for three bins. Additionally, we present a lower bound of $45/33=1.overline36$ for Online Bin Stretching on three bins and a lower bound of $19/14$ for four and five bins that were discovered using a computer search.

Recommendations

• Better Algorithms for Online Bin Stretching
• A two-phase algorithm for bin stretching with stretching factor 1.5
• On-line bin-stretching
• Approximation and Online Algorithms
• Online bin stretching with bunch techniques

Cites work

• A two-phase algorithm for bin stretching with stretching factor 1.5
• 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 bin-stretching
• On-Line Load Balancing for Related Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Online bin stretching with bunch techniques
• Preemptive online scheduling: Optimal algorithms for all speeds
• Semi on-line algorithms for the partition problem
• Semi-online scheduling revisited

Cited in

(14)

• Bin stretching revisited
• A survey on makespan minimization in semi-online environments
• Tight upper bounds for semi-online scheduling on two uniform machines with known optimum
• A two-phase algorithm for bin stretching with stretching factor 1.5
• An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time
• Discovering and certifying lower bounds for the online bin stretching problem
• Tight lower bounds for semi-online scheduling on two uniform machines with known optimum
• Improved lower bounds for the online bin stretching problem
• Online bin stretching with bunch techniques
• On-line bin-stretching
• Bin stretching with migration on two hierarchical machines
• Online early work maximization on three hierarchical machines with a common due date
• Semi-online multiprocessor scheduling with known largest job processing time
• Improved online load balancing with known makespan

This page was built for publication: Online bin stretching with three bins

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