# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 5 A PTAS for the Budget Fence Problem and a Special Case of the Firefighter Problem
For any \(\delta,\epsilon>0\), the firefighter problem in \(P\) can be approximated within \(2\lceil\log_{1+\delta}\frac{\max_{B}}{\min_{B}}\rceil(1+\delta)(1+\epsilon)\) in polynomial time, under the assumption that the chosen barriers have pairwise disjoint interiors. For \(i=1,...,\lceil\log_{1+\delta}\frac{\max_{B}}{\min_{B}}\rceil-1\), divide \(B\) into classes \(B_{i}\) such that the geodesic distance between the barriers in \(B_{i}\) and the fire source falls in the interval \([min_{B}(1+\delta)^{i},\ \min_{B}(1+\delta)^{i+1}]\). There exists \(j\in\{1,...,\lceil\log_{1+\delta}\frac{\max_{B}}{\min_{B}}\rceil-1\}\) such that the barriers in \(B_{j}\) save at least \(\frac{1}{\lceil\log_{1+\delta}\frac{\max_{B}}{\min_{B}}\rceil}\) of the area saved by an optimal solution to the geometric firefighter instance. Therefore, it is sufficient to approximate within \(2(1+\delta)(1+\epsilon)\) an optimal solution \(O_{i}\) to the instance constrained to barriers in \(B_{i}\) for \(i=1,...,\lceil\log_{1+\delta}\frac{\max_{B}}{\min_{B}}\rceil\), and then choose the best solution in order to obtain the corollary. Fix \(i\in\{1,...,\lceil\log_{1+\delta}\frac{\max_{B}}{\min_{B}}\rceil\}\). First, find a set of at most \(k\) barriers in \(B_{i}\) that jointly save the largest area. This can be easily done in polynomial time. If \(O_{i}\) contains at most \(k\) barriers which jointly save at least \(\frac{1}{2}\) area saved by \(O_{i}\) then we are done. To handle the opposite case, we proceed as follows. Let \(t\) be the time it takes for the fire to reach the geodesic distance \(\min_{B}(1+\delta)^{i+1}\) from the source. Note that \(O_{i}\) contains at most one barrier that is finished after the time \(t\) elapsed. For proof's sake, remove such a barrier (if any) and all the barriers that need at least \(\frac{t}{k-1}\) time to be build. Let \(O^{\prime}_{i}\) be the resulting set of barriers. Since at most \(k\) barriers have been removed, the barriers in \(O^{\prime}_{i}\) save at least half the area saved by \(O_{i}\). Sort the barriers in \(O^{\prime}_{i}\) by their ratio between the saved area and barrier length in non-decreasing order. Consider the maximum prefix of the sorted sequence of barriers that can be build within the time \(t/(1+\delta)\). By the definition of the sorted sequence, the area saved by the barriers in the prefix is at least \(\frac{1}{1+\delta}-\frac{1}{k-1}\) of the area saved by the barriers in \(O^{\prime}_{i}\). We can pick \(k\) sufficiently large so the area saved by the barriers in the prefix is at least \(\frac{1}{(1+\delta)\sqrt{1+\epsilon}}\) of that saved by the barriers in \(O^{\prime}_{i}\). We can obtain at least \(\sqrt{1+\epsilon}\) approximation of the area saved by the barriers in the prefix by running our PTAS for the budget fence problem on the polygon \(P\) with the set of allowed barriers \(B_{i}\) and the length constraint equal to the time \(t/(1+\delta)\) multiplied by the speed of building a barrier. Consequently, we obtain an \(2(1+\delta)(1+\epsilon)\) approximation of \(O_{i}\).