---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Rudolf
foaf_name: Ahlswede, Rudolf
foaf_surname: Ahlswede
foaf_workInfoHomepage: http://www.librecat.org/personId=10479
- foaf_Person:
foaf_givenName: Ferdinando
foaf_name: Cicalese, Ferdinando
foaf_surname: Cicalese
- foaf_Person:
foaf_givenName: Christian
foaf_name: Deppe, Christian
foaf_surname: Deppe
foaf_workInfoHomepage: http://www.librecat.org/personId=10503
bibo_doi: 10.1016/j.dam.2007.04.033
bibo_issue: '9'
bibo_volume: '156'
dct_date: 2008^xs_gYear
dct_identifier:
- UT:000255804200008
dct_isPartOf:
- http://id.crossref.org/issn/0166-218X
dct_language: eng
dct_publisher: Elsevier@
dct_subject:
- searching with lies
- coding with feedback
dct_title: Searching with lies under error cost constraints@
...