### 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 | |

State | Published - 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

Chang, E. C., & Yap, C. (2000). A simultaneous search problem.

*Algorithmica (New York)*,*26*(2), 255-262. https://doi.org/10.1007/s004539910012