A simultaneous search problem

E. C. Chang; C. Yap

doi:10.1007/s004539910012

A simultaneous search problem

E. C. Chang, C. Yap

Computer Science

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

Abstract

We introduce a new search problem motivated by computational metrology. The problem is as follows: we would like to locate two unknown numbers x, y ε [0, 1] with as little uncertainty as possible, using some given number k of probes. Each probe is specified by a real numbe r ε [0, 1]. After a probe at r, we arc told whether x ≤ r or x ≥ r, and whether y ≤ r or y ≥ r. We derive the optimal strategy and prove that the asymptotic behavior of the total uncertainty after it probes is 13/7 2^-(k+1)/2 for odd k and 13/10 2^-k/2 for even it.

Original language	English (US)
Pages (from-to)	255-262
Number of pages	8
Journal	Algorithmica (New York)
Volume	26
Issue number	2
DOIs	https://doi.org/10.1007/s004539910012
State	Published - 2000

Keywords

Algorithm
Binary search
Comparison model
Metrology
Probe model

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s004539910012

Cite this

@article{c9d42d0d90ce48d8af4b500abdfc4161,

title = "A simultaneous search problem",

abstract = "We introduce a new search problem motivated by computational metrology. The problem is as follows: we would like to locate two unknown numbers x, y ε [0, 1] with as little uncertainty as possible, using some given number k of probes. Each probe is specified by a real numbe r ε [0, 1]. After a probe at r, we arc told whether x ≤ r or x ≥ r, and whether y ≤ r or y ≥ r. We derive the optimal strategy and prove that the asymptotic behavior of the total uncertainty after it probes is 13/7 2-(k+1)/2 for odd k and 13/10 2-k/2 for even it.",

keywords = "Algorithm, Binary search, Comparison model, Metrology, Probe model",

author = "Chang, {E. C.} and C. Yap",

year = "2000",

doi = "10.1007/s004539910012",

language = "English (US)",

volume = "26",

pages = "255--262",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - A simultaneous search problem

AU - Chang, E. C.

AU - Yap, C.

PY - 2000

Y1 - 2000

N2 - We introduce a new search problem motivated by computational metrology. The problem is as follows: we would like to locate two unknown numbers x, y ε [0, 1] with as little uncertainty as possible, using some given number k of probes. Each probe is specified by a real numbe r ε [0, 1]. After a probe at r, we arc told whether x ≤ r or x ≥ r, and whether y ≤ r or y ≥ r. We derive the optimal strategy and prove that the asymptotic behavior of the total uncertainty after it probes is 13/7 2-(k+1)/2 for odd k and 13/10 2-k/2 for even it.

AB - We introduce a new search problem motivated by computational metrology. The problem is as follows: we would like to locate two unknown numbers x, y ε [0, 1] with as little uncertainty as possible, using some given number k of probes. Each probe is specified by a real numbe r ε [0, 1]. After a probe at r, we arc told whether x ≤ r or x ≥ r, and whether y ≤ r or y ≥ r. We derive the optimal strategy and prove that the asymptotic behavior of the total uncertainty after it probes is 13/7 2-(k+1)/2 for odd k and 13/10 2-k/2 for even it.

KW - Algorithm

KW - Binary search

KW - Comparison model

KW - Metrology

KW - Probe model

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

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

U2 - 10.1007/s004539910012

DO - 10.1007/s004539910012

M3 - Article

AN - SCOPUS:8444246316

SN - 0178-4617

VL - 26

SP - 255

EP - 262

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 2

ER -

A simultaneous search problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this