Improved online algorithms for one-dimensional BinPacking with advice

Xiaofan Zhao, Xin Li, Hong Shen

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

Abstract

In this paper, we study the problem of 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 the work of Boyar et al. of competitive ratio 4/3 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 als, we can obtain an online algorithm with competitive ratio 5/4 to pack list L. Furthermore, we show that our algorithm can retain the same competitive ratio 5/4 with only two advice bits per item, hence improving the known result.

Original languageEnglish
Title of host publicationProceedings - 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2017
EditorsShi-Jinn Horng
PublisherIEEE Computer Society
Pages211-216
Number of pages6
ISBN (Electronic)9781538631515
DOIs
Publication statusPublished - 2 Jul 2017
Externally publishedYes
Event18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2017 - Taipei, Taiwan, Province of China
Duration: 18 Dec 201720 Dec 2017

Publication series

NameParallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings
Volume2017-December

Conference

Conference18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2017
Country/TerritoryTaiwan, Province of China
CityTaipei
Period18/12/1720/12/17

Keywords

  • Bin packing
  • Competitive ratio
  • Computation with advice
  • Online algorithm

Fingerprint

Dive into the research topics of 'Improved online algorithms for one-dimensional BinPacking with advice'. Together they form a unique fingerprint.

Cite this