Advanced

Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.

Klein, Rolf; Levcopoulos, Christos LU and Lingas, Andrzej LU (2014) LATIN 2014: Theoretical Informatics, 11th Latin American Symposium In LATIN 2014: Theoretical Informatics /Lecture Notes in Computer Science 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)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
LATIN 2014: Theoretical Informatics /Lecture Notes in Computer Science
editor
Pardo, Alberto; Viola, Alberto; and
volume
8392
pages
12 pages
publisher
Springer
conference name
LATIN 2014: Theoretical Informatics, 11th Latin American Symposium
external identifiers
  • scopus:84899925143
ISSN
1611-3349
0302-9743
DOI
10.1007/978-3-642-54423-1_23
language
English
LU publication?
yes
id
d08a53ee-515e-4372-8eb5-24e6b3801eaa (old id 7990542)
date added to LUP
2015-09-24 14:52:58
date last changed
2017-04-09 03:14:16
@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         = {1611-3349},
  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},
  volume       = {8392},
  year         = {2014},
}