A simultaneous search problem

E. C. Chang, C. Yap

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)255-262
Number of pages8
JournalAlgorithmica (New York)
Volume26
Issue number2
DOIs
StatePublished - 2000

Keywords

  • Algorithm
  • Binary search
  • Comparison model
  • Metrology
  • Probe model

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A simultaneous search problem'. Together they form a unique fingerprint.

  • Cite this