Better Algorithms for Online Bin Stretching
conference contribution
posted on 2015-06-01, 10:31 authored by Martin Böhm, Jin Sgall, Rob van Stee, Pavel Veselý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.
History
Citation
Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wroc\law, Poland, September 11-12, 2014, Revised Selected Papers, 2014, pp. 23-34Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer ScienceVersion
- AM (Accepted Manuscript)
Published in
Approximation and Online Algorithms - 12th International WorkshopPublisher
Springer International Publishingisbn
978-3-319-18262-9;978-3-319-18263-6Copyright date
2015Available date
2016-04-23Publisher DOI
Publisher version
http://link.springer.com/chapter/10.1007/978-3-319-18263-6_3Notes
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-18263-6_3Book series
Lecture Notes in Computer Science;8952Language
enAdministrator link
Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC