Article

A robust APTAS for the classical bin packing problem

Authors:

Asaf LevinAuthors Info & Claims

ICALP'06: Proceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part I

Pages 214 - 225

https://doi.org/10.1007/11786986_20

Published: 10 July 2006 Publication History

Abstract

Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions.

References

[1]

E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: A survey. In D. Hochbaum, editor, Approximation algorithms. PWS Publishing Company, 1997.

Digital Library

[2]

J. Csirik and G. J. Woeginger. On-line packing and covering problems. In A. Fiat and G. J. Woeginger, editors, Online Algorithms: The State of the Art, pages 147-177, 1998.

Digital Library

[3]

W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1+ε in linear time. Combinatorica, 1:349-355, 1981.

[4]

G. Galambos and G. J. Woeginger. Repacking helps in bounded space online bin packing. Computing, 49:329-338, 1993.

[5]

G. Gambosi, A. Postiglione, and M. Talamo. On-line maintenance of an approximate bin-packing solution. Nordic Journal on Computing, 4(2):151-166, 1997.

[6]

G. Gambosi, A. Postiglione, and M. Talamo. Algorithms for the relaxed online bin-packing model. SIAM Journal on Computing, 30(5):1532-1551, 2000.

Digital Library

[7]

D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems: theoretical and practical results. Journal of the ACM, 34(1):144-162, 1987.

Digital Library

[8]

Z. Ivkovic and E. L. Lloyd. Partially dynamic bin packing can be solved within 1 + ε in (amortized) polylogarithmic time. Information Processing Letters, 63(1):45-50, 1997.

Digital Library

[9]

Z. Ivkovic and E. L. Lloyd. Fully dynamic algorithms for bin packing: Being (mostly) myopic helps. SIAM Journal on Computing, 28(2):574-611, 1998.

Digital Library

[10]

N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS'82), pages 312-320, 1982.

Digital Library

[11]

C. C. Lee and D. T. Lee. A simple online bin packing algorithm. Journal of the ACM, 32(3):562-572, 1985.

Digital Library

[12]

P. Sanders, N. Sivadasan, and M. Skutella. Online scheduling with bounded migration. In Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP2004), pages 1111-1122, 2004.

[13]

A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, 1986.

Digital Library

[14]

S. S. Seiden. On the online bin packing problem. Journal of the ACM, 49(5):640- 671, 2002.

Digital Library

[15]

J. D. Ullman. The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ, 1971.

[16]

A. van Vliet. An improved lower bound for online bin packing algorithms. Information Processing Letters, 43(5):277-284, 1992.

Digital Library

[17]

V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.

Digital Library

Cited By

Bender MFarach-Colton MFekete SFineman JGilbert SBlelloch GAgrawal K(2015)Cost-Oblivious Reallocation for Scheduling and PlanningProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755589(143-154)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2755573.2755589
Sanders PSivadasan NSkutella M(2009)Online Scheduling with Bounded MigrationMathematics of Operations Research10.1287/moor.1090.038134:2(481-498)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1287/moor.1090.0381
Shachnai HYehezkely O(2007)Fast asymptotic FPTAS for packing fragmentable items with costsProceedings of the 16th international conference on Fundamentals of Computation Theory10.5555/2391495.2391539(482-493)Online publication date: 27-Aug-2007
https://dl.acm.org/doi/10.5555/2391495.2391539

Recommendations

A robust APTAS for the classical bin packing problem

Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution ...
An APTAS for Generalized Cost Variable-Sized Bin Packing

Bin packing is a well-known problem which has a large number of applications. Classical bin packing is a simple model in which all bins are identical. In the bin packing problem with variable-sized bins, we are given a supply of a variety of sizes. This ...
There is no APTAS for 2-dimensional vector bin packing: Revisited
Abstract
We study the Vector Bin Packing and the Vector Bin Covering problems, multidimensional generalizations of the Bin Packing and the Bin Covering problems, respectively. In the Vector Bin Packing, we are given a set of d-dimensional ...
Highlights
- Vector Bin Packing has no asymptotic PTAS.
- The proof provided fixes an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'06: Proceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part I

July 2006

729 pages

ISBN:3540359044

Editors:
Michele Bugliesi
Dipartimento di Informatica, Università Ca' Foscari, Venice
,
Bart Preneel
Dipartimento di Informatica, Interdisciplinary Institute for BroadBand Technology (IBBT), Belgium
,
Vladimiro Sassone
ECS, University of Southampton, Belgium, UK
,
Ingo Wegener
FB Informatik, Univ. Dortmund, Dortmund, Germany

Sponsors

Università Ca'Foscari: Università Ca'Foscari
IBM Italy: IBM Italy
Consorzio Venezia Ricerche: Consorzio Venezia Ricerche
Venis S.P.A - Venezia Informatica e Sistemi: Venis S.P.A - Venezia Informatica e Sistemi

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 July 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bender MFarach-Colton MFekete SFineman JGilbert SBlelloch GAgrawal K(2015)Cost-Oblivious Reallocation for Scheduling and PlanningProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755589(143-154)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2755573.2755589
Sanders PSivadasan NSkutella M(2009)Online Scheduling with Bounded MigrationMathematics of Operations Research10.1287/moor.1090.038134:2(481-498)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1287/moor.1090.0381
Shachnai HYehezkely O(2007)Fast asymptotic FPTAS for packing fragmentable items with costsProceedings of the 16th international conference on Fundamentals of Computation Theory10.5555/2391495.2391539(482-493)Online publication date: 27-Aug-2007
https://dl.acm.org/doi/10.5555/2391495.2391539

View Options

View options

Media

Figures

Other

Tables

View Table of Contents