Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
Klein, Rolf ; Levcopoulos, Christos LU
and Lingas, Andrzej
LU
(2018)
In Algorithms
11(4).
- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/a8bb4fed-75be-4c72-8695-f8942448194a
- author
- Klein, Rolf
; Levcopoulos, Christos
LU
and Lingas, Andrzej
LU
- organization
- publishing date
- 2018-04-11
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Algorithms
- volume
- 11
- issue
- 4
- article number
- 45
- publisher
- MDPI AG
- external identifiers
-
- scopus:85069868840
- ISSN
- 1999-4893
- DOI
- 10.3390/a11040045
- language
- English
- LU publication?
- yes
- id
- a8bb4fed-75be-4c72-8695-f8942448194a
- date added to LUP
- 2018-04-12 17:54:47
- date last changed
- 2022-04-25 06:53:21
@article{a8bb4fed-75be-4c72-8695-f8942448194a,
abstract = {{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.}},
author = {{Klein, Rolf and Levcopoulos, Christos and Lingas, Andrzej}},
issn = {{1999-4893}},
language = {{eng}},
month = {{04}},
number = {{4}},
publisher = {{MDPI AG}},
series = {{Algorithms}},
title = {{Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems}},
url = {{http://dx.doi.org/10.3390/a11040045}},
doi = {{10.3390/a11040045}},
volume = {{11}},
year = {{2018}},
}