Wiener, Gábor
Rounds in Combinatorial Search
Abstract
The search complexity of a separating system ${cal H} subseteq 2^{[m]}$ is the minimum number of questions of type ``$xin H$? hinspace '' (where $H in {cal H}$) needed in the worst case to determine a hidden element $xin [m]$.
If we are allowed to ask the questions in at most $k$ batches then we speak of the emph{$k$round} (or emph{$k$stage}) complexity of ${cal H}$, denoted by $hbox{c}_k ({cal H})$. While $1$round and $m$round complexities (called nonadaptive and adaptive complexities, respectively) are widely studied (see for example Aigner cite{A}), much less is known about other possible values of $k$, though the cases with small values of $k$ (tipically $k=2$) attracted significant attention recently, due to their applications in DNA library screening.
It is clear that
$ {cal H} geq hbox{c}_{1} ({cal H}) geq hbox{c}_{2} ({cal H}) geq ldots geq hbox{c}_{m} ({cal H})$.
A group of problems raised by {G. O. H. Katona} cite{Ka} is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems ${cal H}$ with the property ${cal H} = hbox{c}_{k} ({cal H}) $ for any $kgeq 3$. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.
BibTeX  Entry
@InProceedings{wiener:DSP:2009:2239,
author = {G{\'a}bor Wiener},
title = {Rounds in Combinatorial Search},
booktitle = {Search Methodologies },
year = {2009},
editor = {Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
number = {09281},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2239},
annote = {Keywords: Search, group testing, adaptiveness, hypergraph, trace}
}
2009
Keywords: 

Search, group testing, adaptiveness, hypergraph, trace 
Seminar: 

09281  Search Methodologies

Issue date: 

2009 
Date of publication: 

2009 