Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.

Klein, Rolf ; Levcopoulos, Christos LU orcid and Lingas, Andrzej LU (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)
Please use this url to cite or link to this publication:
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
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
2016-04-01 10:32:43
date last changed
2024-12-02 13:56:37
@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}},
  doi          = {{10.1007/978-3-642-54423-1_23}},
  volume       = {{8392}},
  year         = {{2014}},
}