Approximation algorithms for the geometric firefighter and budget fence problems
Summary: Let \(R\) denote a connected region inside a simple polygon, \(P\). By building barriers (typically straight-line segments) in \(P \backslash R\), we want to separate from \(R\) part(s) of \(P\) of maximum area. All edges of the boundary of \(P\) are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the \textit{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 \textit{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 certain conditions. Even for simple cases (e.g., \(P\) is a convex polygon and \(B\) the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient \(\approx 11.65\) approximation algorithm for the firefighter problem, where the set \(B\) of allowed barriers is any set of straight-line segments with all endpoints on the boundary of \(P\) and pairwise disjoint interiors. Since this algorithm solves a much more general problem -- a hybrid of scheduling and maximum coverage -- it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross.
- A constant factor approximation algorithm for generalized MIN-sum set cover
- A threshold of ln n for approximating set cover
- Algorithms – ESA 2005
- Approximability of the firefighter problem. Computing cuts over time
- Approximation algorithms for the geometric firefighter and budget fence problems
- Finding exact solutions for the geometric firefighter problem in practice
- Firefighting on a random geometric graph
- Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On a fire fighter's problem
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- The budgeted maximum coverage problem
- The complexity of separating points in the plane
- The firefighter problem for graphs of maximum degree three
- The Firefighter problem: a survey of results, directions and questions
- The generalized maximum coverage problem
- The geometry of scheduling
- Towards more efficient infection and fire fighting
- Finding exact solutions for the geometric firefighter problem in practice
- A near-quadratic algorithm for fence design
- Surviving rate of graphs and firefighter problem
- Approximation algorithms for the geometric firefighter and budget fence problems
- Geometric firefighting in the half-plane
- Exact solutions for the moving firefighter problem on trees
This page was built for publication: Approximation algorithms for the geometric firefighter and budget fence problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2331446)
