License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09281.6
URN: urn:nbn:de:0030-drops-22399
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2239/
Go to the corresponding Portal

Wiener, Gábor

Rounds in Combinatorial Search

pdf-format:
09281.WienerGabor.ExtAbstract.2239.pdf (0.2 MB)

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:DagSemProc.09281.6,
  author =	{Wiener, G\'{a}bor},
  title =	{{Rounds in Combinatorial Search}},
  booktitle =	{Search Methodologies},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/2239},
  URN =		{urn:nbn:de:0030-drops-22399},
  doi =		{10.4230/DagSemProc.09281.6},
  annote =	{Keywords: Search, group testing, adaptiveness, hypergraph, trace}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI