| Paper ID | D7-S5-T1.2 |
| Paper Title |
Non-Adaptive and Adaptive Two-Sided Search with Fast Objects |
| Authors |
Alexey Lebedev, Russian Academy of Sciences, Russia; Christian Deppe, Technical University Munich, Germany |
| Session |
D7-S5-T1: Combinatorics |
| Chaired Session: |
Tuesday, 20 July, 23:20 - 23:40 |
| Engagement Session: |
Tuesday, 20 July, 23:40 - 00:00 |
| Abstract |
Koopman introduced in 1946 a two-sided search model. In this search model, the searched object is active and can move one step after each test at most. In this paper we analyze the model of a combinatorial two-sided search by allowing more moves of the searched object after each test. We give search strategies and show that these strategies are optimal. We consider adaptive and non-adaptive strategies. We show the surprising result that with the combinatorial two-sided search on a path graph the optimal non-adaptive search needs the same number of questions as the corresponding adaptive search strategy does. The strategy obtained can also be used to transmit the position of a moving element through a channel. Furthermore, the strategy is a generalization of a group testing strategy to a moving searched element.
|
