---
_id: '1587893'
abstract:
- lang: eng
text: 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.
alternative_id:
- '2427242'
- '1860131'
author:
- first_name: Rudolf
full_name: Ahlswede, Rudolf
id: '10479'
last_name: Ahlswede
- first_name: Ferdinando
full_name: Cicalese, Ferdinando
last_name: Cicalese
- first_name: Christian
full_name: Deppe, Christian
id: '10503'
last_name: Deppe
citation:
ama: Ahlswede R, Cicalese F, Deppe C. Searching with lies under error cost constraints.
*Discrete Applied Mathematics*. 2008;156(9):1444-1460.
angewandte-chemie: R. Ahlswede, F. Cicalese, and C. Deppe, “Searching with lies
under error cost constraints”, *Discrete Applied Mathematics*, **2008**,
*156*, 1444-1460.
apa: 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
apa_indent: 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

aps: ' R. Ahlswede, F. Cicalese, and C. Deppe, Searching with lies under error
cost constraints, Discrete Applied Mathematics **156**, 1444 (2008).'
bio1: 'Ahlswede R, Cicalese F, Deppe C (2008)

Searching with lies under error
cost constraints.

Discrete Applied Mathematics 156(9): 1444-1460.'
chicago: 'Ahlswede,
Rudolf, Cicalese, Ferdinando, and Deppe, Christian. 2008. “Searching with lies
under error cost constraints”. *Discrete Applied Mathematics* 156 (9):
1444-1460.

'
default: 'Ahlswede R, Cicalese F, Deppe C (2008)

*Discrete Applied Mathematics*
156(9): 1444-1460.'
dgps: Ahlswede,
R., Cicalese, F. & Deppe, C. (2008). Searching with lies under error cost
constraints. *Discrete Applied Mathematics*, *156*(9), 1444-1460.
Elsevier. doi:10.1016/j.dam.2007.04.033.

frontiers: Ahlswede, R., Cicalese, F., and Deppe, C. (2008). Searching with lies
under error cost constraints. *Discrete Applied Mathematics* 156, 1444-1460.
harvard1: Ahlswede, R., Cicalese, F., & Deppe, C., 2008. Searching with lies
under error cost constraints. *Discrete Applied Mathematics*, 156(9), p
1444-1460.
ieee: ' R. Ahlswede, F. Cicalese, and C. Deppe, “Searching with lies under error
cost constraints”, *Discrete Applied Mathematics*, vol. 156, 2008, pp.
1444-1460.'
lncs: ' Ahlswede, R., Cicalese, F., Deppe, C.: Searching with lies under error cost
constraints. Discrete Applied Mathematics. 156, 1444-1460 (2008).'
mla: 'Ahlswede, Rudolf, Cicalese, Ferdinando, and Deppe, Christian. “Searching with
lies under error cost constraints”. *Discrete Applied Mathematics* 156.9
(2008): 1444-1460.'
wels: 'Ahlswede, R.; Cicalese, F.; Deppe, C. (2008): Searching with lies under error
cost constraints *Discrete Applied Mathematics*,156:(9): 1444-1460.'
date_created: 2010-04-26T09:44:15Z
date_updated: 2018-07-24T12:58:28Z
department:
- _id: '10020'
doi: 10.1016/j.dam.2007.04.033
edit_mode: expert
external_id:
isi:
- '000255804200008'
first_author: Ahlswede, Rudolf
intvolume: ' 156'
isi: '1'
issue: '9'
keyword:
- searching with lies
- coding with feedback
language:
- iso: eng
page: 1444-1460
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: Searching with lies under error cost constraints
type: journal_article
volume: '156'
year: '2008'
...