Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/32322
Title: Better Algorithms for Online Bin Stretching
Authors: Böhm, Martin
Sgall, Jin
Stee, Rob van
Veselý, Pavel
First Published: 23-Apr-2015
Publisher: Springer International Publishing
Citation: Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wroc\law, Poland, September 11-12, 2014, Revised Selected Papers, 2014, pp. 23-34
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 the 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 also show a specialized algorithm for three bins with a stretching factor of 11=8 = 1:375.
Series/Report no.: Lecture Notes in Computer Science;8952
DOI Link: 10.1007/978-3-319-18263-6_3
ISBN: 978-3-319-18262-9
Links: http://link.springer.com/chapter/10.1007%2F978-3-319-18263-6_3
http://hdl.handle.net/2381/32322
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2015, Springer Verlag. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Description: The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-18263-6_3
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
stretch-waoa.pdfPost-review (final submitted)136.82 kBUnknownView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.