Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems

Let R denote a connected region inside a simple polygon, P. By building 1-dimensional barriers in P ∖ R, we want to separate from R part(s) of P of maximum area. In this paper we introduce two versions of this problem. In the budget fence version the regi

  • PDF / 233,709 Bytes
  • 12 Pages / 439.363 x 666.131 pts Page_size
  • 25 Downloads / 195 Views

DOWNLOAD

REPORT


2

Universit¨ at Bonn, Institut f¨ ur Informatik I, D-53117 Bonn [email protected] Department of Computer Science, Lund University, 22100 Lund {Christos.Levcopoulos,Andrzej.Lingas}@cs.lth.se

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 R part(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 B that 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.

1

Introduction

The firefighter problem in graphs has recently received significant attention [2,7,11,13]. It models a situation where a fire, infection, computer virus, etc., spreads through a network, and the goal is to save as many network nodes as possible by a suitable placement of firefighters. At the beginning a fire breaks out at the source vertex of the input graph. At each subsequent time step a bounded number of firefighters (just one in the standard version) may be placed at vertices that are not already on fire, to defend them. Once defended, a vertex will never catch fire. After the firefighters have been placed, the fire spreads from each burning vertex to all its undefended neighbors. The process ends when the fire can no longer spread. All vertices which are not on fire are considered to be saved. The objective is to determine a placement of firefighters that maximizes the number of vertices saved. A. Pardo and A. Viola (Eds.): LATIN 2014, LNCS 8392, pp. 261–272, 2014. c Springer-Verlag Berlin Heidelberg 2014 

262

R. Klein, C. Levcopoulos, and A. Lingas

This graph firefighter problem is NP-hard already for trees [11,12], and hard to approximate within nα , for any α < 1, in polynomial-time in the general case [7]. Only trees are known to admit polynomial-time constant-factor (e/(e − 1) ≈ 1.5819) approximation algorithms [7]. In this paper we propose a natural geometric firefighter problem. Instead of a graph, we have a polygonal region P with a distinguished point R where a fire starts spreading thr

Data Loading...