On the sum-of-squares algorithm for bin packing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the sum-of-squares algorithm for bin packing

Full text

Pdf (1.12 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 208 - 217

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Janos Csirik	Department of Computer Sciences, University of Szeged, Szeged, Hungary
David S. Johnson	AT&T Labs, Room C239, 180, Park Avenue, Florham Park, NJ
Claire Kenyon	Laboratoire de Recherche en Informatique, Bâtiment 490, Université Paris-Sud, 91405 Orsay Cedex, France
James B. Orlin	Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA
Peter W. Shor	AT&T Labs, Room C237, 180, Park Avenue, Florham Park, NJ
Richard R. Weber	Statistical Laboratory, University of Cambridge, Cambridge CB2 1SB, England

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 40, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335331 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Susanne Albers , Michael Mitzenmacher, Average-case analyses of first fit and random fit bin packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.290-299, January 25-27, 1998, San Francisco, California, United States
	2	E. G. Coffman, Jr. , C. Courcoubetis , M. R. Garey , D. S. Johnson , L. A. McGeoch , P. W. Shor , R. R. Weber , M. Yannakakis, Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.230-240, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103446]
	3	E. G. Coffman, Jr. , C. Courcoubetis , M. R. Garey , D. S. Johnson , P. W. Shor , R. R. Weber , M. Yannakakis, Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings, SIAM Journal on Discrete Mathematics, v.13 n.3, p.384-402, May—June 2000 [doi>10.1137/S0895480197325936]
	4	E. G. Coffman, Jr., D. S. Johnson, L. A. McGeoch, P. W. Shor, and R. R. Weber. Bin packing with discrete item sizes, Part III: Average-case behavior of FFD and BFD. In preparation.
	5	E. G. Coffman, Jr. , D. S. Johnson , P. W. Shor , R. R. Weber, Markov chains, computer proofs, and average-case analysis of best fit bin packing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.412-421, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167203]
	6	E. G. Coffman, Jr. , D. S. Johnson , P. W. Shor , R. R. Weber, Bin packing with discrete item sizes, part II: tight bounds on first fit, Random Structures & Algorithms, v.10 n.1-2, p.69-101, Jan.–March 1997 [doi>10.1002/(SICI)1098-2418(199701/03)10:1/2<69::AID-RSA4>3.0.CO;2-V]
	7	C. Courcoubetis and R. R. Weber. Stability of on-line bin packing with random arrivals and long-run average constraints. Prob. Eng. Inf. Sci., 4:447-460, 1990.
	8	János Csirik , David S. Johnson , Claire Kenyon , Peter W. Shor , Richard R. Weber, A Self Organizing Bin Packing Heuristic, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.246-265, January 15-16, 1999
	9	W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1 +e in linear time. Combinatorica, 1:349-355, 1981.
	10	B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Prob., 14:502-525, 1982.
	11	N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin packing problem. In Proc. 23rd Ann. Syrup. on Foundations of Computer Science, pages 312-320, 1982. IEEE Computer Soc.
	12	Claire Kenyon , Yuval Rabani , Alistair Sinclair, Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing, Journal of Algorithms, v.27 n.2, p.218-235, May 1, 1998 [doi>10.1006/jagm.1997.0919]
	13	Wansoo T. Rhee, Optimal bin packing with items of random sizes, Mathematics of Operations Research, v.13 n.1, p.140-151, February 1988 [doi>10.1287/moor.13.1.140]
	14	Wansoo T. Rhee , Michel Talagrand, On line bin packing with items of random size, Mathematics of Operations Research, v.18 n.2, p.438-445, May 1993 [doi>10.1287/moor.18.2.438]
	15	Wansoo T. Rhee , Michel Talagrand, On-line bin packing of items of random sizes, II, SIAM Journal on Computing, v.22 n.6, p.1251-1256, Dec. 1993 [doi>10.1137/0222074]
	16	P. M. Vaidya. Speeding-up linear programming using fast matrix multiplication. In Proceedings, The 30th Annual Symposium on Foundations of Computer Science, pages 332-337, Los Alamitos, CA, 1989. IEEE Computer Society Press.
	17	D. B. Wilson. Personal communication, 2000.

CITED BY 2

	Janos Csirik , David S. Johnson , Claire Kenyon, Better approximation algorithms for bin covering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.557-566, January 07-09, 2001, Washington, D.C., United States
	Gu Xiaodong , Chen Guoliang , Xu Yinlong, Deep performance analysis of refined harmonic bin packing algorithm, Journal of Computer Science and Technology, v.17 n.2, p.213-218, March 2002