Two-bounded-space bin packing revisited

M. Chrobak, J. Sgall, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)
1 Downloads (Pure)

Abstract

We analyze approximation algorithms for bounded-space bin packing by comparing them against the optimal bounded-space packing (instead of comparing them against the globally optimal packing that does not necessarily satisfy the bounded-space constraint). For 2-bounded-space bin packing we construct a polynomial time offline approximation algorithm with asymptotic worst case ratio 3/2, and we show a lower bound of 5/4 for this scenario. We show that no 2-bounded-space online algorithm can have an asymptotic worst case ratio better than 4/3.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2011 (19th Annual European Symposium, Ljubljana, Slovenia, September 5-9, 2011. Proceedings)
EditorsC. Demetrescu, M.H. Halldorsson
Place of PublicationBerlin
PublisherSpringer
Pages263-274
ISBN (Print)978-3-642-23718-8
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6942
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Two-bounded-space bin packing revisited'. Together they form a unique fingerprint.

Cite this