Online Bin Packing with Advice

Joan Boyar, Shahin Kamali, Kim Skak Larsen, Alejandro López-Ortiz

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publication31st Symposium on Theoretical Aspects of Computer Science, STACS 2014
EditorsErnst W. Mayr, Natacha Portier
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Publication date1. Mar 2014
ISBN (Electronic)978-3-939897-65-1
Publication statusPublished - 1. Mar 2014
EventInternational Symposium on Theoretical Aspects of Computer Science - Lyon, France
Duration: 5. Mar 20148. Mar 2014
Conference number: 31


ConferenceInternational Symposium on Theoretical Aspects of Computer Science
SeriesLeibniz International Proceedings in Informatics


Dive into the research topics of 'Online Bin Packing with Advice'. Together they form a unique fingerprint.

Cite this