Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.
(2014) LATIN 2014: Theoretical Informatics, 11th Latin American Symposium In LATIN 2014: Theoretical Informatics /Lecture Notes in Computer Science 8392. p.261272 Abstract
 Let R denote a connected region inside a simple polygon, P. By building 1dimensional 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 1dimensional 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 NPhard. 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 polynomialtime 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:
http://lup.lub.lu.se/record/7990542
 author
 Klein, Rolf; Levcopoulos, Christos ^{LU} and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2014
 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
 16113349
 03029743
 DOI
 10.1007/9783642544231_23
 language
 English
 LU publication?
 yes
 id
 d08a53ee515e43728eb524e6b3801eaa (old id 7990542)
 date added to LUP
 20150924 14:52:58
 date last changed
 20180107 04:04:40
@inproceedings{d08a53ee515e43728eb524e6b3801eaa, abstract = {Let R denote a connected region inside a simple polygon, P. By building 1dimensional 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 NPhard. 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 polynomialtime 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 = {16113349}, language = {eng}, pages = {261272}, publisher = {Springer}, title = {Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.}, url = {http://dx.doi.org/10.1007/9783642544231_23}, volume = {8392}, year = {2014}, }