More Web Proxy on the site http://driver.im/

research-article

Bin packing via discrepancy of permutations

Authors:

Friedrich Eisenbrand,

Dömötör Pálvölgyi,

Thomas RothvoßAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 476 - 481

Published: 23 January 2011 Publication History

Abstract

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins.

The three-permutations-conjecture of Beck is the following. Given any 3 permutations on n symbols, one can color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols differs only by a constant. Beck's conjecture is well known in the field of discrepancy theory.

We establish a surprising connection between bin packing and Beck's conjecture: If the latter holds true, then the additive integrality gap of the 3-partition linear programming relaxation is bounded by a constant.

References

[1]

W. Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures Algorithms, 12(4):351--360, 1998.

Digital Library

[2]

N. Bansal. Constructive algorithms for discrepancy minimization. CoRR, abs/1002.2259, 2010. informal publication.

[3]

J. Beck and T. Fiala. "Integer-making" theorems. Discrete Appl. Math., 3(1): 1--8, 1981.

[4]

J. Beck and V. Sós. Discrepancy theory. In Handbook of combinatorics, Vol. 1, 2, pages 1405--1446. Elsevier, Amsterdam, 1995.

Digital Library

[5]

G. Bohus. On the discrepancy of 3 permutations. Random Structures Algorithms, 1(2):215--220, 1990.

[6]

R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, 1997.

[7]

G. Dósa. The tight bound of first fit decreasing bin-packing algorithm is FFD(I) <= 11/9OPT(I) + 6/9. In Bo Chen, Mike Paterson, and Guochuan Zhang, editors, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, First International Symposium, ESCAPE 2007, Hangzhou, China, April 7--9, 2007, Revised Selected Papers, volume 4614 of Lecture Notes in Computer Science, pages 1--11. Springer, 2007.

Digital Library

[8]

K. Eisemann. The trim problem. Management Science, 3(3):279--284, 1957.

[9]

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

[10]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, New York, 1979.

Digital Library

[11]

P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Operations Research, 9:849--859, 1961.

[12]

M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169--197, 1981.

[13]

K. Jansen and R. Solis-Oba. An opt + 1 algorithm for the cutting stock problem with constant number of object lengths. In Friedrich Eisenbrand and F. Bruce Shepherd, editors, Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010, pages 438--449, 2010.

Digital Library

[14]

D. S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973.

[15]

D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299--325, 1974.

[16]

N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982), pages 312--320. IEEE, New York, 1982.

Digital Library

[17]

L. Lovász, J. Spencer, and K. Vesztergombi. Discrepancy of set-systems and matrices. European J. Combin., 7(2):151--160, 1986.

Digital Library

[18]

J. Matoušek. Geometric discrepancy, volume 18 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1999. An illustrated guide.

[19]

G. Scheithauer and J. Terno. Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem. Operations Research Letters, 20(2):93--100, 1997.

Digital Library

[20]

A. Sebő and G. Shmonin. Proof of the modified integer round-up conjecture for bin packing in dimension 7. Personal communication, 2009.

[21]

J. Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society, 289(2):679--706, 1985.

[22]

J. H. Spencer, A. Srinivasan, and P. Tetali. The discrepancy of permutation families. Unpublished manuscript.

[23]

A. Srinivasan. Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'97 (New Orleans, Louisiana, January 5--7, 1997), pages 692--701, Philadelphia, PA, 1997. ACM SIGACT, SIAM, Society for Industrial and Applied Mathematics.

Digital Library

[24]

D. Williamson. Lecture notes on approximation algorithms, Fall 1998. IBM Research Report, 1998. http://legacy.orie.cornell.edu/~dpw/cornell.ps

Cited By

Hoberg RRothvoss TKlein P(2017)A logarithmic additive integrality gap for bin packingProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039858(2616-2625)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039858
Eisenbrand FPálvölgyi DRothvoß T(2013)Bin Packing via Discrepancy of PermutationsACM Transactions on Algorithms10.1145/2483699.24837049:3(1-15)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2483699.2483704
Verschae JWiese A(2011)On the configuration-LP for scheduling on unrelated machinesProceedings of the 19th European conference on Algorithms10.5555/2040572.2040631(530-542)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040631
Show More Cited By

Bin packing via discrepancy of permutations

Recommendations

Bin Packing via Discrepancy of Permutations
Special Issue on SODA'11

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP ...
Better Bin Packing Approximations via Discrepancy Theory

For bin packing, the input consists of $n$ items with sizes $s_1,\ldots,s_n \in [0,1]$ which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar--Karp algorithm from 1982 produces a solution with at most $OPT + O(\log^2 OPT)$ ...
Strip Packing vs. Bin Packing
AAIM '07: Proceedings of the 3rd international conference on Algorithmic Aspects in Information and Management

In this paper we establish a general algorithmic framework between bin packing and strip packing, with which we achieve the same asymptotic bounds by applying bin packing algorithms to strip packing. More precisely we obtain the following results: (1) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
66
Total Downloads

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

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hoberg RRothvoss TKlein P(2017)A logarithmic additive integrality gap for bin packingProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039858(2616-2625)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039858
Eisenbrand FPálvölgyi DRothvoß T(2013)Bin Packing via Discrepancy of PermutationsACM Transactions on Algorithms10.1145/2483699.24837049:3(1-15)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2483699.2483704
Verschae JWiese A(2011)On the configuration-LP for scheduling on unrelated machinesProceedings of the 19th European conference on Algorithms10.5555/2040572.2040631(530-542)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040631
Bansal NKrishnaswamy RSaha B(2011)On capacitated set cover problemsProceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques10.5555/2033252.2033257(38-49)Online publication date: 17-Aug-2011
https://dl.acm.org/doi/10.5555/2033252.2033257
Eisenbrand FKakimura NRothvoß TSanità L(2011)Set covering with ordered replacementProceedings of the 15th international conference on Integer programming and combinatoral optimization10.5555/2018158.2018172(170-182)Online publication date: 15-Jun-2011
https://dl.acm.org/doi/10.5555/2018158.2018172

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents