File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Selecting the k largest elements with parity tests

TitleSelecting the k largest elements with parity tests
Authors
Lam, TWTing, HF
KeywordsLower Bound
Parity Tests
Randomized Algorithm
Selection
Issue Date2000
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/dam
Citation
Discrete Applied Mathematics, 2000, v. 101 n. 1-3, p. 187-196 How to Cite?
DOI: http://dx.doi.org/10.1016/S0166-218X(99)00193-6
AbstractIn this paper we study the problem of finding the k largest elements of n distinct real numbers. We give a pure combinatorial argument to prove that n+(k-1)logn+O(1) queries are necessary for any deterministic algorithm using parity tests only. We also present a randomized algorithm with error probability O(1/nc) using only O(log2n+klogn) parity tests, where c>1 is any fixed constant. © 2000 Elsevier Science B.V.
Persistent Identifierhttp://hdl.handle.net/10722/152310
ISSN
0166-218X
2023 Impact Factor: 1.0
2023 SCImago Journal Rankings: 0.657
ISI Accession Number ID
WOS:000085777500012
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_US
dc.contributor.authorTing, HFen_US
dc.date.accessioned2012-06-26T06:37:05Z-
dc.date.available2012-06-26T06:37:05Z-
dc.date.issued2000en_US
dc.identifier.citationDiscrete Applied Mathematics, 2000, v. 101 n. 1-3, p. 187-196en_US
dc.identifier.issn0166-218Xen_US
dc.identifier.urihttp://hdl.handle.net/10722/152310-
dc.description.abstractIn this paper we study the problem of finding the k largest elements of n distinct real numbers. We give a pure combinatorial argument to prove that n+(k-1)logn+O(1) queries are necessary for any deterministic algorithm using parity tests only. We also present a randomized algorithm with error probability O(1/nc) using only O(log2n+klogn) parity tests, where c>1 is any fixed constant. © 2000 Elsevier Science B.V.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/damen_US
dc.relation.ispartofDiscrete Applied Mathematicsen_US
dc.subjectLower Bounden_US
dc.subjectParity Testsen_US
dc.subjectRandomized Algorithmen_US
dc.subjectSelectionen_US
dc.titleSelecting the k largest elements with parity testsen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.emailTing, HF:hfting@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/S0166-218X(99)00193-6-
dc.identifier.scopuseid_2-s2.0-0347304330en_US
dc.identifier.hkuros51953-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0347304330&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume101en_US
dc.identifier.issue1-3en_US
dc.identifier.spage187en_US
dc.identifier.epage196en_US
dc.identifier.isiWOS:000085777500012-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.issnl0166-218X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats