Searching with lies under error cost constraints

Ahlswede R, Cicalese F, Deppe C (2008)
Discrete Applied Mathematics 156(9): 1444-1460.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor/in
Abstract / Bemerkung
The Wnyi-Berlekamp-Ulam game is a classical model for the problem of determining the minimum number of queries to find an unknown member in a finite set when up to a finite number of the answers may be erroneous. In the variant considered in this paper, questions with q many possible answers are allowed, further lies are constrained by a bipartite graph with edges weighted by 0, 1, 2.... (the "channel"). The channel Gamma is an arbitrary assignment stipulating the cost of the different possible lies, i.e., of each answer j not equal i when the correct answer is i by Gamma(i, j). It is also assumed that a maximum cost a (sum of the cost of all wrong answers) can be afforded by the responder during the whole game. We provide tight asymptotic bounds for the number of questions needed to solve this problem. The appropriate searching strategies are actually provided. We also show that adaptiveness can be dramatically reduced when the channel satisfies certain symmetry constraints. (C) 2007 Elsevier B.V. All rights reserved.
Stichworte
searching with lies; coding with feedback
Erscheinungsjahr
2008
Zeitschriftentitel
Discrete Applied Mathematics
Band
156
Ausgabe
9
Seite(n)
1444-1460
ISSN
0166-218X
Page URI
https://pub.uni-bielefeld.de/record/1587893

Zitieren

Ahlswede R, Cicalese F, Deppe C. Searching with lies under error cost constraints. Discrete Applied Mathematics. 2008;156(9):1444-1460.
Ahlswede, R., Cicalese, F., & Deppe, C. (2008). Searching with lies under error cost constraints. Discrete Applied Mathematics, 156(9), 1444-1460. doi:10.1016/j.dam.2007.04.033
Ahlswede, R., Cicalese, F., and Deppe, C. (2008). Searching with lies under error cost constraints. Discrete Applied Mathematics 156, 1444-1460.
Ahlswede, R., Cicalese, F., & Deppe, C., 2008. Searching with lies under error cost constraints. Discrete Applied Mathematics, 156(9), p 1444-1460.
R. Ahlswede, F. Cicalese, and C. Deppe, “Searching with lies under error cost constraints”, Discrete Applied Mathematics, vol. 156, 2008, pp. 1444-1460.
Ahlswede, R., Cicalese, F., Deppe, C.: Searching with lies under error cost constraints. Discrete Applied Mathematics. 156, 1444-1460 (2008).
Ahlswede, Rudolf, Cicalese, Ferdinando, and Deppe, Christian. “Searching with lies under error cost constraints”. Discrete Applied Mathematics 156.9 (2008): 1444-1460.