Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.

In English

Författare

Redaktör

  • 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.

Publiceringsår

2014

Språk

Engelska

Sidor

261-272

Publikation/Tidskrift/Serie

LATIN 2014: Theoretical Informatics /Lecture Notes in Computer Science

Volym

8392

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • 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/Övrigt

  • ISSN: 1611-3349
  • ISSN: 0302-9743