File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A randomized algorithm for finding maximum with O((log n)2) polynomial tests

TitleA randomized algorithm for finding maximum with O((log n)2) polynomial tests
Authors
KeywordsAlgorithms
Decision Trees
Maximum
Parity Tests
Randomized Algorithms
Issue Date1994
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 1994, v. 49 n. 1, p. 39-43 How to Cite?
AbstractA well-known result by Rabin implies that n • 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c> 0, there is a randomized agorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests.
Persistent Identifierhttp://hdl.handle.net/10722/152244
ISSN
2015 Impact Factor: 0.605
2015 SCImago Journal Rankings: 0.698
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorTing, HFen_US
dc.contributor.authorYao, ACen_US
dc.date.accessioned2012-06-26T06:36:43Z-
dc.date.available2012-06-26T06:36:43Z-
dc.date.issued1994en_US
dc.identifier.citationInformation Processing Letters, 1994, v. 49 n. 1, p. 39-43en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://hdl.handle.net/10722/152244-
dc.description.abstractA well-known result by Rabin implies that n • 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c> 0, there is a randomized agorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_US
dc.relation.ispartofInformation Processing Lettersen_US
dc.subjectAlgorithmsen_US
dc.subjectDecision Treesen_US
dc.subjectMaximumen_US
dc.subjectParity Testsen_US
dc.subjectRandomized Algorithmsen_US
dc.titleA randomized algorithm for finding maximum with O((log n)2) polynomial testsen_US
dc.typeArticleen_US
dc.identifier.emailTing, HF:hfting@cs.hku.hken_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/0020-0190(94)90052-3en_US
dc.identifier.scopuseid_2-s2.0-0028199378en_US
dc.identifier.volume49en_US
dc.identifier.issue1en_US
dc.identifier.spage39en_US
dc.identifier.epage43en_US
dc.identifier.isiWOS:A1994MV42200007-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.scopusauthoridYao, AC=7101796460en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats