Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.
Author
Editor
- Alberto Pardo
- Alberto Viola
Summary, in English
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.
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.
Department/s
Publishing year
2014
Language
English
Pages
261-272
Publication/Series
LATIN 2014: Theoretical Informatics /Lecture Notes in Computer Science
Volume
8392
Document type
Conference paper
Publisher
Springer
Topic
- Computer Science
Conference name
LATIN 2014: Theoretical Informatics, 11th Latin American Symposium
Conference date
2014-03-31
Conference place
Montevideo, Uruguay
Status
Published
ISBN/ISSN/Other
- ISSN: 1611-3349
- ISSN: 0302-9743