Please use this identifier to cite or link to this item:
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
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
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.