License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-22399
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2239/
Go to the corresponding Portal

Wiener, Gábor

Rounds in Combinatorial Search

pdf-format:
Document 1.pdf (173 KB)

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 non-adaptive 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 =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2239},
  annote =	{Keywords: Search, group testing, adaptiveness, hypergraph, trace}
}

Keywords: Search, group testing, adaptiveness, hypergraph, trace
Seminar: 09281 - Search Methodologies
Issue Date: 2009
Date of publication: 10.11.2009

DROPS-Home | Fulltext Search | Imprint Published by LZI