All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD7-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.