Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in P \ R , we want to separate from R part(s) of...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-04-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/11/4/45 |
| _version_ | 1818538817685028864 |
|---|---|
| author | Rolf Klein Christos Levcopoulos Andrzej Lingas |
| author_facet | Rolf Klein Christos Levcopoulos Andrzej Lingas |
| author_sort | Rolf Klein |
| collection | DOAJ |
| description | Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in
P
\
R
, we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈11.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross. |
| first_indexed | 2024-12-11T21:33:53Z |
| format | Article |
| id | doaj.art-368fb35ba31b43d2a4ebd686cf3436dc |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-11T21:33:53Z |
| publishDate | 2018-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-368fb35ba31b43d2a4ebd686cf3436dc2022-12-22T00:50:04ZengMDPI AGAlgorithms1999-48932018-04-011144510.3390/a11040045a11040045Approximation Algorithms for the Geometric Firefighter and Budget Fence ProblemsRolf Klein0Christos Levcopoulos1Andrzej Lingas2Institut für Informatik I, Universität Bonn, D-53117 Bonn, GermanyDepartment of Computer Science, Lund University, 221 00 Lund, SwedenDepartment of Computer Science, Lund University, 221 00 Lund, SwedenLet R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in P \ R , we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈11.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross.http://www.mdpi.com/1999-4893/11/4/45budget fence problemfirefighter problemPTASschedulingset covertime complexity |
| spellingShingle | Rolf Klein Christos Levcopoulos Andrzej Lingas Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems Algorithms budget fence problem firefighter problem PTAS scheduling set cover time complexity |
| title | Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems |
| title_full | Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems |
| title_fullStr | Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems |
| title_full_unstemmed | Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems |
| title_short | Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems |
| title_sort | approximation algorithms for the geometric firefighter and budget fence problems |
| topic | budget fence problem firefighter problem PTAS scheduling set cover time complexity |
| url | http://www.mdpi.com/1999-4893/11/4/45 |
| work_keys_str_mv | AT rolfklein approximationalgorithmsforthegeometricfirefighterandbudgetfenceproblems AT christoslevcopoulos approximationalgorithmsforthegeometricfirefighterandbudgetfenceproblems AT andrzejlingas approximationalgorithmsforthegeometricfirefighterandbudgetfenceproblems |