Online Bin Packing with Advice.

Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
In 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 174-186. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2014.

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 + epsilon. 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 5/4.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): none.

full version

Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.

open access (197 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.