Two-bounded-space bin packing revisited

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelAlgorithms - ESA 2011 (19th Annual European Symposium, Ljubljana, Slovenia, September 5-9, 2011. Proceedings)
RedacteurenC. Demetrescu, M.H. Halldorsson
Plaats van productieBerlin
UitgeverijSpringer
Pagina's263-274
ISBN van geprinte versie978-3-642-23718-8
DOI's
StatusGepubliceerd - 2011

Publicatie series

NaamLecture Notes in Computer Science
Volume6942
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Two-bounded-space bin packing revisited'. Samen vormen ze een unieke vingerafdruk.

Citeer dit