Finding an approximate maximum

Research output: Contribution to journalArticle

4 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)258-267
Number of pages10
JournalSIAM Journal on Computing
Volume18
Issue number2
DOIs
StatePublished - Jan 1 1989
Externally publishedYes

Fingerprint

Binary
Sufficient
Necessary

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science(all)

Cite this

Alon, Noga Mordechai ; Azar, Y. / Finding an approximate maximum. In: SIAM Journal on Computing. 1989 ; Vol. 18, No. 2. pp. 258-267.
@article{c4e5f9f311174cc7bfc42e4df8d73ba3,
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 = "Alon, {Noga Mordechai} and Y. Azar",
year = "1989",
month = "1",
day = "1",
doi = "https://doi.org/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",

}

Finding an approximate maximum. / Alon, Noga Mordechai; Azar, Y.

In: SIAM Journal on Computing, Vol. 18, No. 2, 01.01.1989, p. 258-267.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Finding an approximate maximum

AU - Alon, Noga Mordechai

AU - Azar, Y.

PY - 1989/1/1

Y1 - 1989/1/1

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 - https://doi.org/10.1137/0218017

DO - https://doi.org/10.1137/0218017

M3 - Article

VL - 18

SP - 258

EP - 267

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 2

ER -