Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.

; and (2014) LATIN 2014: Theoretical Informatics, 11th Latin American Symposium 8392. p.261-272
Abstract
Let R denote a connected region inside a simple polygon, P. By building 1-dimensional barriers in P ∖ R, we want to separate from Rpart(s) of P of maximum area. 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 Bthat satisfies a certain linearity condition. For... (More)
Let R denote a connected region inside a simple polygon, P. By building 1-dimensional barriers in P ∖ R, we want to separate from Rpart(s) of P of maximum area. 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 Bthat satisfies a certain linearity condition. For example, this condition is satisfied for barrier curves in general position, if any two barriers cross at most once.

Even for simple cases (e. g., P 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. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider application. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from B must not cross. (Less)
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
LATIN 2014: Theoretical Informatics /Lecture Notes in Computer Science
editor
Pardo, Alberto and Viola, Alberto
volume
8392
pages
12 pages
publisher
Springer
conference name
LATIN 2014: Theoretical Informatics, 11th Latin American Symposium
conference location
Montevideo, Uruguay
conference dates
2014-03-31
external identifiers
• scopus:84899925143
ISSN
0302-9743
1611-3349
DOI
10.1007/978-3-642-54423-1_23
language
English
LU publication?
yes
id
d08a53ee-515e-4372-8eb5-24e6b3801eaa (old id 7990542)
2016-04-01 10:32:43
date last changed
2021-10-06 03:30:24
```@inproceedings{d08a53ee-515e-4372-8eb5-24e6b3801eaa,
abstract     = {Let R denote a connected region inside a simple polygon, P. By building 1-dimensional barriers in P ∖ R, we want to separate from Rpart(s) of P of maximum area. 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 Bthat satisfies a certain linearity condition. For example, this condition is satisfied for barrier curves in general position, if any two barriers cross at most once.<br/><br>
<br/><br>
Even for simple cases (e. g., P 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. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider application. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from B must not cross.},
author       = {Klein, Rolf and Levcopoulos, Christos and Lingas, Andrzej},
booktitle    = {LATIN 2014: Theoretical Informatics /Lecture Notes in Computer Science},
editor       = {Pardo, Alberto and Viola, Alberto},
issn         = {0302-9743},
language     = {eng},
pages        = {261--272},
publisher    = {Springer},
title        = {Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.},
url          = {http://dx.doi.org/10.1007/978-3-642-54423-1_23},
doi          = {10.1007/978-3-642-54423-1_23},
volume       = {8392},
year         = {2014},
}

```