Approximation Algorithms for Anchored Multiwatchman Routes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910584561205248 |
|---|---|
| author | Mitchell, Joseph S. B. Nguyen, Linh |
| author_facet | Mitchell, Joseph S. B. Nguyen, Linh |
| contents | We study some variants of the $k$-\textsc{Watchman Routes} problem, the cooperative version of the classic \textsc{Watchman Routes} problem in a simple polygon. The watchmen may be required to see the whole polygon, or some pre-determined quota of area within the polygon, and we want to minimize the maximum length traveled by any watchman. While the single watchman version of the problem has received much attention is rather well understood, it is not the case for multiple watchmen version.
We provide the first tight approximability results for the anchored $k$-\textsc{Watchman Routes} problem in a simple polygon, assuming $k$ is fixed, by a fully-polynomial time approximation scheme. The basis for the FPTAS is provided by an exact dynamic programming algorithm. If $k$ is a variable, we give constant-factor approximations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_17343 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for Anchored Multiwatchman Routes Mitchell, Joseph S. B. Nguyen, Linh Computational Geometry We study some variants of the $k$-\textsc{Watchman Routes} problem, the cooperative version of the classic \textsc{Watchman Routes} problem in a simple polygon. The watchmen may be required to see the whole polygon, or some pre-determined quota of area within the polygon, and we want to minimize the maximum length traveled by any watchman. While the single watchman version of the problem has received much attention is rather well understood, it is not the case for multiple watchmen version. We provide the first tight approximability results for the anchored $k$-\textsc{Watchman Routes} problem in a simple polygon, assuming $k$ is fixed, by a fully-polynomial time approximation scheme. The basis for the FPTAS is provided by an exact dynamic programming algorithm. If $k$ is a variable, we give constant-factor approximations. |
| title | Approximation Algorithms for Anchored Multiwatchman Routes |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2408.17343 |