1 Search Results for "Kübel, David"

Document
DOI: 10.4230/LIPIcs.SWAT.2016.19
Optimal Online Escape Path Against a Certificate

Authors: Elmar Langetepe and David Kübel

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
More than fifty years ago Bellman asked for the best escape path within a known forest but for an unknown starting position. This deterministic finite path is the shortest path that leads out of a given environment from any starting point. There are some worst case positions where the full path length is required. Up to now such a fixed ultimate optimal escape path for a known shape for any starting position is only known for some special convex shapes (i.e., circles, strips of a given width, fat convex bodies, some isosceles triangles). Therefore, we introduce a different, simple and intuitive escape path, the so-called certificate path which make use of some additional information w.r.t. the starting point s. This escape path depends on the starting position s and takes the distances from s to the outer boundary of the environment into account. Because of this, in the above convex examples the certificate path always (for any position s) leaves the environment earlier than the ultimate escape path. Next we assume that neither the precise shape of the environment nor the location of the starting point is not known, we have much less information. For a class of environments (convex shapes and shapes with kernel positions) we design an online strategy that always leaves the environment. We show that the path length for leaving the environment is always shorter than 3.318764 the length of the corresponding certificate path. We also give a lower bound of 3.313126 which shows that for the above class of environments the factor 3.318764 is (almost) tight.
Cite as

Elmar Langetepe and David Kübel. Optimal Online Escape Path Against a Certificate. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{langetepe_et_al:LIPIcs.SWAT.2016.19,
  author =	{Langetepe, Elmar and K\"{u}bel, David},
  title =	{{Optimal Online Escape Path Against a Certificate}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.19},
  URN =		{urn:nbn:de:0030-drops-60414},
  doi =		{10.4230/LIPIcs.SWAT.2016.19},
  annote =	{Keywords: Search games, online algorithms, escape path, competitive analysis, spiral conjecture}
}
  • Refine by Author
  • 1 Kübel, David
  • 1 Langetepe, Elmar

  • Refine by Classification

  • Refine by Keyword
  • 1 Search games
  • 1 competitive analysis
  • 1 escape path
  • 1 online algorithms
  • 1 spiral conjecture

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact