License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.8
URN: urn:nbn:de:0030-drops-83033
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8303/
Borodin, Allan ;
Pankratov, Denis ;
Salehi-Abari, Amirali
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version
Abstract
Recently, Renault (2016) studied the dual bin packing problem in the per-request advice model of online algorithms. He showed that given O(1/eps) advice bits for each input item allows approximating the dual bin packing problem online to within a factor of 1+\eps. Renault asked about the advice complexity of dual bin packing in the tape-advice model of online algorithms. We make progress on this question. Let s be the maximum bit size of an input item weight. We present a conceptually simple online algorithm that with total advice O((s + log n)/eps^2) approximates the dual bin packing to within a 1+eps factor. To this end, we describe and analyze a simple offline PTAS for the dual bin packing problem. Although a PTAS for a more general problem was known prior to our work (Kellerer 1999, Chekuri and Khanna 2006), our PTAS is arguably simpler to state and analyze. As a result, we could easily adapt our PTAS to obtain the advice-complexity result.
We also consider whether the dependence on s is necessary in our algorithm. We show that if s is unrestricted then for small enough eps > 0 obtaining a 1+eps approximation to the dual bin packing requires Omega_eps(n) bits of advice. To establish this lower bound we analyze an online reduction that preserves the advice complexity and approximation ratio from the binary separation problem due to Boyar et al. (2016). We define two natural advice complexity classes that capture the distinction similar to the Turing machine world distinction between pseudo polynomial time algorithms and polynomial time algorithms. Our results on the dual bin packing problem imply the separation of the two classes in the advice complexity world.
BibTeX - Entry
@InProceedings{borodin_et_al:OASIcs:2018:8303,
author = {Allan Borodin and Denis Pankratov and Amirali Salehi-Abari},
title = {{A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version}},
booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)},
pages = {8:1--8:12},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-064-4},
ISSN = {2190-6807},
year = {2018},
volume = {61},
editor = {Raimund Seidel},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8303},
URN = {urn:nbn:de:0030-drops-83033},
doi = {10.4230/OASIcs.SOSA.2018.8},
annote = {Keywords: dual bin packing, PTAS, tape-advice complexity}
}
|
Keywords: |
|
dual bin packing, PTAS, tape-advice complexity |
|
Collection: |
|
1st Symposium on Simplicity in Algorithms (SOSA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
05.01.2018 |
