Better Algorithms for Online Bin Stretching

DOI10.1007/978-3-319-18263-6_3MaRDI QIDQ3453280zbMATH OpenOpenAlexFDO

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

Publication date 20 November 2015

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2381/32322

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Recommendations

• Improved lower bounds for the online bin stretching problem
• An efficient algorithm for bin stretching
• A new and improved algorithm for online bin packing
• Discovering and certifying lower bounds for the online bin stretching problem
• Comparing online algorithms for bin packing problems
• Online bin packing: old algorithms and new results
• Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing
• An improved lower bound for on-line bin packing algorithms
• New Bounds for Variable-Sized Online Bin Packing
• Online algorithms for a dual version of bin packing

Cites work

• An efficient algorithm for bin stretching
• On-Line Load Balancing for Related Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Preemptive online scheduling: Optimal algorithms for all speeds
• Semi on-line algorithms for the partition problem

Cited in

(10)

• Bin stretching revisited
• A two-phase algorithm for bin stretching with stretching factor 1.5
• Online bin stretching with three bins
• 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
• An efficient algorithm for bin stretching
• Online bin stretching with bunch techniques
• On-line bin-stretching
• An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

This page was built for publication: Better Algorithms for Online Bin Stretching

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