Fundamental discrepancies between average-case analyses under discrete and continuous distributions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study

Full text

Pdf (1.31 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 230 - 240

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

E. G. Coffman, Jr.	AT&T Bell Labs., Murray Hill, NJ
C. Courcoubetis	AT&T Bell Labs., Murray Hill, NJ
M. R. Garey	AT&T Bell Labs., Murray Hill, NJ
D. S. Johnson	AT&T Bell Labs., Murray Hill, NJ
L. A. McGeoch	Amherst College, Amherst, MA
P. W. Shor	AT&T Bell Labs., Murray Hill, NJ
R. R. Weber	Cambridge Univ., Cambridge, UK
M. Yannakakis	AT&T Bell Labs., Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 36, Citation Count: 11

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/103418.103446 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	M. A.rrAI, J. KOML6S, AND G. TUSNADY, "On optimal matchings," Combinatorica 4 (1983), 259-264.
	2	J. L. BENTLEY, D. S. JOHNSON, F. T. LEIGHTON, AND C. C. McGEocH, "An experimental study of bin packing," in Proc. 21st Ann. Allerton Conf. on Communication, Control, and Computing, University of Illinois, Urbana, IL, 1983, 51- 60.
	3	J. L. Bentley , D. S. Johnson , F. T. Leighton , C. C. McGeoch , L. A. McGeoch, Some unexpected expected behavior results for bin packing, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.279-288, December 1984 [doi>10.1145/800057.808692]
	4	E. G. COFFMAN, JR, M. HoFRI, K. So, AN# A. C. YAO, "A stochastic model of bin packing," Information and Control 44 (1980), 105-115.
	5	C. COURCOUBETIS AND R. R. WEBER, "Necessary and sufficient conditions for the stability of a bin-packing system," J. Appl. Prob. 23 (1986), 989-999.
	6	C. COURCOUBETIS AND R. R. WEBER, "Stability of flexible manufacturing systems," Operations Res., to appear.
	7	J. Csm_rK, J. B. G. F-'m#NK, A. FRmZE, G. GALAMBOS, AND A. H. G. RINNOOY KAN, "A probabilistic analysis of the next fit decreasing bin packing heuristic," Operations Res. Lett. 5 (1986), 233-236.
	8	J. Csirik , D. S. Johnson, Bounded space on-line bin packing: best is better than first, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.309-319, January 28-30, 1991, San Francisco, California, United States
	9	G. N. FREDERICKSON, "Probabilistic analysis for simple oneand two-dimensional bin packing algorithms," Inform. Process. Lett. 11 (1980), 156-161.
	10	G. H. HARDY AND J. E. LrrrLEWOOD, "Some problems of Diophantine approximation," Acta Mathematica 37 (1914), 155-238.
	11	B. HAJEK, "Hitting-time and occupation-time bounds implied by drift analysis with applications," Adv. Appl. Prob. 14 (1982), 502-525.
	12	N. KARMARKAR, "Probabilistic analysis of some bin-packing algorithms," in "Proceedings 23rd Ann. Symp. on Foundations of Computer Science," IEEE Computer Society, Los Angeles, Calif., 1982, 107-111.
	13	Richard M. Karp , Michael Luby , A. Marchetti-Spaccamela, A probabilistic analysis of multidimensional bin packing problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.289-298, December 1984 [doi>10.1145/800057.808693]
	14	Walter Knödel, A Bin Packing Algorithm with Complexity O(n log n) and Performance 1 in the Stochastic Limit, Proceedings on Mathematical Foundations of Computer Science, p.369-378, August 31-September 04, 1981
	15	Donald E. Knuth, Big Omicron and big Omega and big Theta, ACM SIGACT News, v.8 n.2, p.18-24, April-June 1976 [doi>10.1145/1008328.1008329]
	16	G. S. LUEKER, "An average-case analysis of bin packing with uniformly distributed item sizes," Report No. 181, Department of Information and Computer Science, University of California, Irvine, CA, 1982.
	17	G. S. LUEKER, "Bin packing with items uniformly distributed over intervals {a,b}," in "Proceedings 24th Ann. Syrup. on Foundations of Computer Science," IEEE Computer Society, Los Angeles, Calif., 1983, 289-297.
	18	P. Ramanan, Average-case analysis of the smart next fit algorithm, Information Processing Letters, v.31 n.5, p.221-225, June 12, 1989 [doi>10.1016/0020-0190(89)90077-X]
	19	P. RAMANAN AND K. TSUGA, "Average-case analysis of the modified harmonic algorithm," Algorithmica 4 (1989), 519- 534.
	20	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]
	21	Wansoo T. Rhee , M. Talagrand, Optimal bin packing with items of random sizes II, SIAM Journal on Computing, v.18 n.1, p.139-151, Feb. 1989 [doi>10.1137/0218009]
	22	P W Shor, The average-case analysis of some on-line algorithms for bin packing, Combinatorica, v.6 n.2, p.179-200, 1986 [doi>10.1007/BF02579171]
	23	P. W. SHOR, "How to pack better than best fit: An improved on-line bin packing algorithm," in preparation.

CITED BY 11

	E. G. Coffman, Jr. , A. L. Stolyar, Fluid limits, bin packing, and stochastic analysis of algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.877-878, January 17-19, 1999, Baltimore, Maryland, United States
	Claire Kenyon , Yuval Rabani , Alistair Sinclair, Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.351-358, January 28-30, 1996, Atlanta, Georgia, United States
	Janos Csirik , David S. Johnson , Claire Kenyon , James B. Orlin , Peter W. Shor , Richard R. Weber, On the sum-of-squares algorithm for bin packing, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.208-217, May 21-23, 2000, Portland, Oregon, United States
	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
	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
	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
	Susanne Albers , Bianca Schröder, An experimental study of online scheduling algorithms, Journal of Experimental Algorithmics (JEA), 7, p.3, 2002
	David Gamarnik, Stochastic online binpacking problem: exact conditions for bounded expected queue lengths under the best fit packing heuristic, ACM SIGMETRICS Performance Evaluation Review, v.29 n.3, December 2001
	Janos Csirik , David S. Johnson , Claire Kenyon , James B. Orlin , Peter W. Shor , Richard R. Weber, On the Sum-of-Squares algorithm for bin packing, Journal of the ACM (JACM), v.53 n.1, p.1-65, January 2006
	Claire Kenyon , Michael Mitzenmacher, Linear waste of best fit bin packing on skewed distributions, Random Structures & Algorithms, v.20 n.3, p.441-464, May 2002
	David Gamarnik, Stochastic Bandwidth Packing Process: Stability Conditions via Lyapunov Function Technique, Queueing Systems: Theory and Applications, v.48 n.3-4, p.339-363, November-December 2004