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
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 |