License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.9
URN: urn:nbn:de:0030-drops-57109
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5710/
Go to the corresponding LIPIcs Volume Portal

Angelopoulos, Spyros ; Dürr, Christoph ; Lidbetter, Thomas

The Expanding Search Ratio of a Graph

pdf-format:
10.pdf (0.7 MB)

Abstract

We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. Most of the previous work on this problem considers the pathwise cost formulation, in which the cost incurred by the searcher is the overall time to locate the target, assuming that the searcher moves at unit speed. More recent work introduced the setting of expanding search in which the searcher incurs cost only upon visiting previously unexplored areas of the graph. Such a paradigm is useful in modeling problems in which the cost of re-exploration is negligible (such as coal mining).

In our work we study algorithmic and computational issues of expanding search, for a variety of search environments including general graphs, trees and star-like graphs. In particular, we rely on the deterministic and randomized search ratio as the performance measures of search strategies, which were originally introduced by Koutsoupias and Papadimitriou [ICALP 1996] in the context of pathwise search. The search ratio is essentially the best competitive ratio among all possible strategies. Our main objective is to explore how the transition from pathwise to expanding search affects the competitive analysis, which has applications to optimization problems beyond the strict boundaries of search problems.

BibTeX - Entry

@InProceedings{angelopoulos_et_al:LIPIcs:2016:5710,
  author =	{Spyros Angelopoulos and Christoph D{\"u}rr and Thomas Lidbetter},
  title =	{{The Expanding Search Ratio of a Graph}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5710},
  URN =		{urn:nbn:de:0030-drops-57109},
  doi =		{10.4230/LIPIcs.STACS.2016.9},
  annote =	{Keywords: Search games, randomized algorithms, competitive analysis, game theory}
}

Keywords: Search games, randomized algorithms, competitive analysis, game theory
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

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