Search
Abstract
We consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. As a way of modeling two-dimensional shapes, we restrict our attention to networks that are embedded into partial grids: nodes are placed on the plane at integer coordinates and only nodes at distance one can be adjacent. We give an on-line algorithm for the searchers that allows them to compute a connected and monotone strategy that guarantees searching any unknown partial grid with the use of O(√n) searchers, where n is the number of nodes in the grid. We prove also a lower bound of Ω(√/n logn) in terms of achievable competitive ratio of any on-line algorithm.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Monographic publication
- Type:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Title of issue:
- Approximation and Online Algorithms - 15th International Workshop strony 223 - 237
- Language:
- English
- Publication year:
- 2018
- Bibliographic description:
- Dereniowski D., URBAŃSKA D.: On-line Search in Two-Dimensional Environment// Approximation and Online Algorithms/ ed. Roberto Solis-Oba, Rudolf Fleischer Cham: , 2018, s.223-237
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/978-3-319-89441-6_17
- Verified by:
- Gdańsk University of Technology
seen 125 times