A Counting Approach to Lower Bounds for Selection Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Counting Approach to Lower Bounds for Selection Problems

Full text

Pdf (640 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 2 (April 1979) table of contents

Pages: 227 - 238

Year of Publication: 1979

ISSN:0004-5411

Authors

Frank Fussenegger	G4250, Martin Marietta Data Systems, P O Box 179, Denver, CO
Harold N. Gabow	Department of Computer Science, University of Colorado at Boulder, Boulder, CO

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/322123.322128 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	BLUM, M, FLOYD, R., PRATT, V., RIVEST, R., AND TAILIAN, R Time bounds for selection J Comptr Syst Scz 7 (1973), 448-461
	2	DOBKIN, D, AND LIPTON, R On the complexity of computations under varying sets of pnmmves Res Rep 42, Dept Comptr Scl, Yale U, New Haven, Corm, 1975
	3	DOBraN, D, AND MUNRO, J I. Tmae and space bounds for selecuon problems Preprmt
	4	FRIEDMAN, N Some results on the effect of anthmeUcs on comparison problems Proc 13th Annual Symp Switching and Automata Theory, College Park, Md, 1972, pp 139-143.
	5	FUSSENEGGER, F, AND GABOW, H N Using comparison trees to derive lower bounds for selecuon problems. Proc 17th Annual Symp Foundations of Comptr Scl, Houston, Tex, 1976, pp 178-182
	6	HYAFIL, L Bounds for selection SIAM J Comping 5 (1976), 109-114
	7	KIRK.PATRICK, D G Topics m the complexity of combmatonal algorithms Tech Rep 74, U of Toronto, Toronto, Ont, Canada, 1974
	8	KISLITSYN, S S On the selecuon of the k-th element of an ordered set by pmrwlse comparisons Stbtrskd Mat Zhurnal 5 (1964), 557-564 (Russian)
	9	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	10	MALANOWICZ, K R. lmprovmg lower bounds for selection problems M.S Th, Dept Comptr So, U of Colorado, Boulder, Colo, 1977
	11	Ira Pohl, A sorting problem and its complexity, Communications of the ACM, v.15 n.6, p.462-464, June 1972 [doi>10.1145/361405.361423]
	12	PRATT, V., AND YAO, F, On lower bounds for computing the t-th largest element Proc 14th Annual Symp Switching and Automata Theory, Iowa City. Iowa, 1973, pp 70--81
	13	RABIN, M O. Proving simultaneous posmvtty of linear forms J Comptr Syst Scl 6 (1972), 639-650
	14	Edward M. Reingold, On the Optimality of Some Set Algorithms, Journal of the ACM (JACM), v.19 n.4, p.649-659, Oct. 1972 [doi>10.1145/321724.321730]
	15	SCHONHAGE, A., PATERSON, M, AND PIPPENGER, N Fmdmg the median J Comptr Syst. Sct, 13 (1976), 184-199
	16	SHAMOS, M I, AND HOEY, D Closest-point problems Proc 16th Annual Symp Foundations of Comptr So., Berkeley, Cahf, 1975, pp 151-162
	17	SPIRA, P M Complete lmear proofs of systems of lmear mequallttes J Comptr. Syst Scl 6 (1972), pp 205- 216
	18	WELLS, M B. Apphcauons of a language for computing mcombmatoncs Information Processing 65, North- Holland Pub Co., Amsterdam, 1965, pp 497-498
	19	YAO, A. On the complexity of companson problems using hnear funcuons Proc 16th Annual Symp Foundations of Comptr. Sc~, Berkeley, Cahf, 1975, pp. 85-89
	20	YAp, C K New lower bounds for median and related problems Res Rep 79, Yale U, New Haven, Conn., 1976.

CITED BY 6

	David G. Kirkpatrick, A Unified Lower Bound for Selection and Set Partitioning Problems, Journal of the ACM (JACM), v.28 n.1, p.150-165, Jan. 1981
	Greg N. Frederickson , Donald B. Johnson, Generalized selection and ranking (Preliminary Version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.420-428, April 28-30, 1980, Los Angeles, California, United States
	Dorit Dor , Uri Zwick, Selecting the median, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 22-24, 1995, San Francisco, California, United States
	S W Bent , J W John, Finding the median requires 2n comparisons, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.213-216, May 06-08, 1985, Providence, Rhode Island, United States
	William Gasarch , Wayne Kelly , William Pugh, Finding the ith largest of n for small i,n, ACM SIGACT News, v.27 n.2, p.88-96, June 1996
	Constantinos Daskalakis , Richard M. Karp , Elchanan Mossel , Samantha Riesenfeld , Elad Verbin, Sorting and selection in posets, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.392-401, January 04-06, 2009, New York, New York