Binary search with delayed and missing answers

✍ Scribed by Ferdinando Cicalese; Ugo Vaccaro

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 95 KB
• Volume: 85
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00426-x

✦ Synopsis

How many questions are necessary and sufficient to guess an unknown number x in the set S = {1, 2, . . . , n}, by using only comparison questions, that is questions of the type "Is x a?", a ∈ S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d 0 and c = 1.