On the advice complexity of one-dimensional online bin packing

Xiaofan Zhao, Hong Shen

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

3 Citations (Scopus)


In this paper, we study the problem of the online bin packing with advice. Assume that there is an oracle with infinite computation power which can provide specific information with regard to each incoming item of the online bin packing problem. With this information, we want to pack the list L of items, one at a time, into a minimum number of bins. The bin capacity is 1 and all items have size no larger than 1. The total size of packed items in each bin cannot exceed the bin capacity. Inspired by Boyar et al's work [1] of competitive ratio [1] with two advice bits per item., we show that if the oracle provides three bits of advice per item, applying a different item classification scheme from Boyar et al's we can obtain an online algorithm with competitive ratio 5/4OPT + 2 to pack list L.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)9783319080154
Publication statusPublished - 2014
Externally publishedYes
Event8th International Frontiers of Algorithmics Workshop, FAW 2014 - Zhangjiajie, China
Duration: 28 Jun 201430 Jun 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8497 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Frontiers of Algorithmics Workshop, FAW 2014


  • bin packing
  • competitive ratio
  • computation with advice
  • online algorithm


Dive into the research topics of 'On the advice complexity of one-dimensional online bin packing'. Together they form a unique fingerprint.

Cite this