Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Boyar, Joan; Kamali, Shahin; Larsen, Kim S.; López-Ortiz, Alejandro http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-44565
URL:

; ; ;

Online Bin Packing with Advice

pdf-format:


Abstract

We consider the online bin packing problem under the advice complexity model where the "online constraint" is relaxed and an algorithm receives partial information about the future requests. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with log(n)+o(log(n)) bits of advice, achieves a competitive ratio of 3/2 for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives 2n+o(n) bits of advice and achieves a competitive ratio of 4/3+e. Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.

BibTeX - Entry

@InProceedings{boyar_et_al:LIPIcs:2014:4456,
  author =	{Joan Boyar and Shahin Kamali and Kim S. Larsen and Alejandro L{\'o}pez-Ortiz},
  title =	{{Online Bin Packing with Advice}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{174--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4456},
  URN =		{urn:nbn:de:0030-drops-44565},
  doi =		{10.4230/LIPIcs.STACS.2014.174},
  annote =	{Keywords: online algorithms, advice complexity, bin packing}
}

Keywords: online algorithms, advice complexity, bin packing
Seminar: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue date: 2014
Date of publication: 2014


DROPS-Home | Fulltext Search | Imprint Published by LZI