Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms

Full text

Pdf (1.32 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 91 - 103

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

F T Leighton	Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
P Shor	Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 24, Citation Count: 10

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/12130.12140 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. Ajtai, J. Komlds, and G. Tusn~dy, "On optimal matchings," Combinatorica, Vol. 4, pp. 259-264, 1983.
	2	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]
	3	J. Blum, "On convergence of empirical distribution functions," Annals of Mathematical Statistics, Vol. 26, pp. 527-529, 1955.
	4	E G Coffman, Jr. , F T Leighton, A provably efficient algorithm for dynamic storage allocation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.77-90, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12139]
	5	P. Diaconis, personal communication, 1985.
	6	R.M. Dudley, "A course in empirical processes," Ecole d'Ete de Probabilitds de Saint-Flour XII, 1982, Lecture Notes in Math. No. 1097, pp. 1-142, Springer Verlag, NY, 1984. (The relevant part is Chapter 8.)
	7	R.M. Dudley, "Empirical and Poisson Processes on classes of sets or functions too large for central limit theorems," Z. Wahrsch. verw. Gebiete 61, pp. 355-368, 1982.
	8	A. Fiat and A. Shamir, "Polymorphic arrays: a novel VLSI layout for systolic computers," Proceedings of the 25th Symp. on Foundations of Computer Science, pp. 37- 45, 1984.
	9	P. Hall, "On representatives of subsets," J. London Math. Soc., Vol. 10, pp. 26-30, 1935.
	10	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]
	11	J. Kiefer, "On the large deviation of the empiric d.f. of vector chance variables and a law of the iterated logarithm," Pacific J. Math., Vol. 11, pp. 649-660, 1961.
	12	F.T. Leighton, 18.419 class notes, 1984.
	13	F.T. Leighton and C.E. Leiserson, "Wafer-scale integration of systolic arrays," IEEE Trans. on Computers, Vol. C-34, No. 5, pp. 448-461, 1985.
	14	M. Lerch, Question 1547, L'Intermgdiare Math., Vol. 11, pp. 145-146, 1904.
	15	M. Luby, personal communication, 1985.
	16	W. Philipp, "Empirical distribution functions and uniform distribution mod 1," Diophantine Approximation and its Applications, C.F. Osgood, ed., Academic Press, NY, 1973.
	17	W. Philipp, personal communication quoted in {6}.
	18	G. Sawitzki, "Another random nunber generator which should be avoided," Statistical Software Newsletters, Vol. 11, No. 2, pp. 81-82 1985.
	19	W. Schmidt, Lectures on Irregularities of Distribution, Tata Institute of Fundamental Research, Bombay, India, 1977.
	20	W. Schmidt, "Irregularities of distribution, VII," Acta Arithmetica, Vol. 21, pp. 45-50, 1972.
	21	P.W. Shor, "The average-case analysis of some on-line algorithms for bin packing," Proceedings of the PSth Syrup. on Foundations of Computer Science, pp. 193-200, 1984.
	22	P.W. Shor, Random Planar Matching and Bin Packing, Ph.D. Thesis, MIT Math. Dept., 1985.
	23	M. Steele, "Limit properties of random variables associated with a partial ordering of Rd, " Annals of Probability, Vol. 5, No. 3, pp. 395-403, 1977.
	24	J. Van der Corput, "Verteilungsfunctionen I.," Proc. Kon. Ned. Akad. v. Wetensch, Vol. 38, pp. 813-821, 1935.
	25	V.N. Vapnik and A. Ya. Cervonenkis, "Necessary and sufficient conditions for the uniform convergences of means to their expectations," Theory of Probability and Applications, Vo}. 26, pp. 532-553, 1981.
	26	F.T. Wright, "The empirical discrepancy over lower layers and a related law of large numbers," Annals of Probability, Vol. 9, pp. 323-329, 1981.

CITED BY 10

	Miron Abramovici , Charles Stroud , Marty Emmert, Using embedded FPGAs for SoC yield improvement, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Richard E. Zippel , Paul Penfield, Jr. , Lance A. Glasser , Charles E. Leiserson , John L. Wyatt, Jr. , F. Thomson Leighton , Jonathan Allen, Recent results in VLSI CAD at MIT, Proceedings of 1986 ACM Fall joint computer conference, p.871-877, November 1986, Dallas, Texas, United States
	Mikhail J. Atallah , Michael T. Goodrich , S. Rao Kosaraju, Parallel algorithms for evaluating sequences of set-manipulation operations, Journal of the ACM (JACM), v.41 n.6, p.1049-1088, Nov. 1994
	John M. Emmert , Dinesh Bhatia, A methodology for fast FPGA floorplanning, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.47-56, February 21-23, 1999, Monterey, California, United States
	E G Coffman, Jr. , F T Leighton, A provably efficient algorithm for dynamic storage allocation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.77-90, May 28-30, 1986, Berkeley, California, United States
	Bruno Codenotti , Roberto Tamassia, A Network Flow Approach to the Reconfiguration of VLSI Arrays, IEEE Transactions on Computers, v.40 n.1, p.118-121, January 1991
	John M. Emmert , Dinesh K. Bhatia, A Fault Tolerant Technique for FPGAs, Journal of Electronic Testing: Theory and Applications, v.16 n.6, p.591-606, Dec. 2000
	John M. Emmert , Charles E. Stroud , Miron Abramovici, Online fault tolerance for FPGA logic blocks, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.2, p.216-226, February 2007
	Amitabha Ghosh , Sajal K. Das, Review: Coverage and connectivity issues in wireless sensor networks: A survey, Pervasive and Mobile Computing, v.4 n.3, p.303-334, June, 2008
	Mauricio Marin , Carlos Gomez, Load balancing distributed inverted files, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal