Finding an approximate maximum

N. Alon; Y. Azar

doi:10.1137/0218017

Finding an approximate maximum

N. Alon, Y. Azar

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

Suppose that there are n elements from a totally ordered domain. The objective is to find, in a minimum possible number of rounds, an element that belongs to the biggest n/2, where in each round one is allowed to ask n binary comparisons. It is shown that log n + Θ(1) rounds are both necessary and sufficient in the best algorithm for this problem.

Original language	English (US)
Pages (from-to)	258-267
Number of pages	10
Journal	SIAM Journal on Computing
Volume	18
Issue number	2
DOIs	https://doi.org/10.1137/0218017
State	Published - 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0218017

Cite this

@article{ef1fbd07ee9e4024be11f2f9b43921de,

title = "Finding an approximate maximum",

abstract = "Suppose that there are n elements from a totally ordered domain. The objective is to find, in a minimum possible number of rounds, an element that belongs to the biggest n/2, where in each round one is allowed to ask n binary comparisons. It is shown that log n + Θ(1) rounds are both necessary and sufficient in the best algorithm for this problem.",

author = "N. Alon and Y. Azar",

year = "1989",

doi = "10.1137/0218017",

language = "English (US)",

volume = "18",

pages = "258--267",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Finding an approximate maximum

AU - Alon, N.

AU - Azar, Y.

PY - 1989

Y1 - 1989

N2 - Suppose that there are n elements from a totally ordered domain. The objective is to find, in a minimum possible number of rounds, an element that belongs to the biggest n/2, where in each round one is allowed to ask n binary comparisons. It is shown that log n + Θ(1) rounds are both necessary and sufficient in the best algorithm for this problem.

AB - Suppose that there are n elements from a totally ordered domain. The objective is to find, in a minimum possible number of rounds, an element that belongs to the biggest n/2, where in each round one is allowed to ask n binary comparisons. It is shown that log n + Θ(1) rounds are both necessary and sufficient in the best algorithm for this problem.

UR - http://www.scopus.com/inward/record.url?scp=0024647378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024647378&partnerID=8YFLogxK

U2 - 10.1137/0218017

DO - 10.1137/0218017

M3 - Article

AN - SCOPUS:0024647378

SN - 0097-5397

VL - 18

SP - 258

EP - 267

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

Finding an approximate maximum

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this