article

Free access

A Counting Approach to Lower Bounds for Selection Problems

Authors:

Frank Fussenegger,

Harold N. GabowAuthors Info & Claims

Journal of the ACM (JACM), Volume 26, Issue 2

Pages 227 - 238

https://doi.org/10.1145/322123.322128

Published: 01 April 1979 Publication History

PDF eReader

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

Google Scholar

[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

Google Scholar

[3]

DOBraN, D, AND MUNRO, J I. Tmae and space bounds for selecuon problems Preprmt

Google Scholar

[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.

Google Scholar

[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

Google Scholar

[6]

HYAFIL, L Bounds for selection SIAM J Comping 5 (1976), 109-114

Google Scholar

[7]

KIRK.PATRICK, D G Topics m the complexity of combmatonal algorithms Tech Rep 74, U of Toronto, Toronto, Ont, Canada, 1974

Google Scholar

[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)

Google Scholar

[9]

KNUTn, D E. The Art of Computer Programming, Vol 3. Sorting and Searching. Addison-Wesley, Reading, Mass, 1973, pp 209-220

Crossref

Google Scholar

[10]

MALANOWICZ, K R. lmprovmg lower bounds for selection problems M.S Th, Dept Comptr So, U of Colorado, Boulder, Colo, 1977

Google Scholar

[11]

POHL, I A sorting problem and its complexity Comm. ACM 15, 6 (June 1972), 462--464

Crossref

Google Scholar

[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

Google Scholar

[13]

RABIN, M O. Proving simultaneous posmvtty of linear forms J Comptr Syst Scl 6 (1972), 639-650

Google Scholar

[14]

REINGOLD, E On the opttmahty of some set algorithms J ACM 19, 4 (Oct 1972), 649-659

Crossref

Google Scholar

[15]

SCHONHAGE, A., PATERSON, M, AND PIPPENGER, N Fmdmg the median J Comptr Syst. Sct, 13 (1976), 184-199

Google Scholar

[16]

SHAMOS, M I, AND HOEY, D Closest-point problems Proc 16th Annual Symp Foundations of Comptr So., Berkeley, Cahf, 1975, pp 151-162

Google Scholar

[17]

SPIRA, P M Complete lmear proofs of systems of lmear mequallttes J Comptr. Syst Scl 6 (1972), pp 205- 216

Google Scholar

[18]

WELLS, M B. Apphcauons of a language for computing mcombmatoncs Information Processing 65, North- Holland Pub Co., Amsterdam, 1965, pp 497-498

Google Scholar

[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

Google Scholar

[20]

YAp, C K New lower bounds for median and related problems Res Rep 79, Yale U, New Haven, Conn., 1976.

Google Scholar

Cited By

View all

Chi-Chih Yao A(2023)On selecting thek largest with median testsAlgorithmica10.1007/BF015538914:1-4(293-300)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01553891
Dumitrescu A(2021)Finding a mediocre playerDiscrete Applied Mathematics10.1016/j.dam.2021.01.006293(15-24)Online publication date: Apr-2021
https://doi.org/10.1016/j.dam.2021.01.006
Chen KDumitrescu A(2020)Selection Algorithms with Small GroupsInternational Journal of Foundations of Computer Science10.1142/S012905412050013631:03(355-369)Online publication date: 1-May-2020
https://doi.org/10.1142/S0129054120500136
Show More Cited By

Index Terms

A Counting Approach to Lower Bounds for Selection Problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration
    2. Graph theory
      1. Trees

Recommendations

On lower bounds for scheduling problems in high-level synthesis
DAC '00: Proceedings of the 37th Annual Design Automation Conference

This paper presents new results on lower bounds for the scheduling problem in high-level synthesis. While several techniques exist for lower bound estimation, comparisons among the techniques have been experimental with few guarantees on the quality of ...
Lower bounds for shellsort
Lower bounds for 2-dimensional range counting
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Proving lower bounds for range queries has been an active topic of research since the late 70s, but so far nearly all results have been limited to the (rather restrictive) semigroup model. We consider one of the most basic range problem, orthogonal ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 26, Issue 2

April 1979

205 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322123

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1979

Published in JACM Volume 26, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
664
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)7

Reflects downloads up to 04 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chi-Chih Yao A(2023)On selecting thek largest with median testsAlgorithmica10.1007/BF015538914:1-4(293-300)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01553891
Dumitrescu A(2021)Finding a mediocre playerDiscrete Applied Mathematics10.1016/j.dam.2021.01.006293(15-24)Online publication date: Apr-2021
https://doi.org/10.1016/j.dam.2021.01.006
Chen KDumitrescu A(2020)Selection Algorithms with Small GroupsInternational Journal of Foundations of Computer Science10.1142/S012905412050013631:03(355-369)Online publication date: 1-May-2020
https://doi.org/10.1142/S0129054120500136
Dumitrescu A(2019)A Selectable Sloppy HeapAlgorithms10.3390/a1203005812:3(58)Online publication date: 6-Mar-2019
https://doi.org/10.3390/a12030058
Dumitrescu A(2019)Finding a Mediocre PlayerAlgorithms and Complexity10.1007/978-3-030-17402-6_18(212-223)Online publication date: 27-May-2019
https://dl.acm.org/doi/10.1007/978-3-030-17402-6_18
Chen KDumitrescu A(2015)Select with Groups of 3 or 4Algorithms and Data Structures10.1007/978-3-319-21840-3_16(189-199)Online publication date: 28-Jul-2015
https://doi.org/10.1007/978-3-319-21840-3_16
Daskalakis CKarp RMossel ERiesenfeld SVerbin E(2011)Sorting and Selection in PosetsSIAM Journal on Computing10.1137/07069772040:3(597-622)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1137/070697720
Mahmoud H(2011)BibliographySorting10.1002/9781118032886.biblio(373-387)Online publication date: 26-Oct-2011
https://doi.org/10.1002/9781118032886.biblio
Daskalakis CKarp RMossel ERiesenfeld SVerbin EMathieu C(2009)Sorting and selection in posetsProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496814(392-401)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496814
Carlsson SChen J(2006)Some lower bounds for comparison-based algorithmsAlgorithms — ESA '9410.1007/BFb0049401(106-117)Online publication date: 23-Feb-2006
https://doi.org/10.1007/BFb0049401
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

References

Cited By

Index Terms

Recommendations

On lower bounds for scheduling problems in high-level synthesis

Lower bounds for shellsort

Lower bounds for 2-dimensional range counting

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations