# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 4 An Approximation Algorithm for the Geometric Firefighter Problem
: _By the above paying scheme, each blue job receives an amount of money not smaller than its property profit._  
Proof. : We define the _efficiency ratio_ of any coloured job \(J\) to be the ratio of its property profit \(\pi\) divided by the duration \(\delta\) of \(J\). Let \(J^{\prime}\) be any blue job. Let us study the iteration of the while-loop when GlobalGreedy considered \(J^{\prime}\) for possible inclusion into the schedule \(L\). Let \(J_{1},J_{2},...,J_{k}\) be the jobs in schedule \(L\) during that step, whose execution times (partially) overlap with the execution time of \(J^{\prime}\). Since \(J^{\prime}\) became a blue job, it was rejected by GlobalGreedy. Thus, the total property profits of \(J_{1},J_{2},...,J_{k}\) must have been be at least \(\mu\) times the red property profit of \(J^{\prime}\), which is no less than \(\mu\) times its current blue property profit because all blue property profits of \(J^{\prime}\) were red during that iteration. Moreover, by the order according to which GlobalGreedy considers jobs for possible insertion into \(L\), it follows that the efficiency ratio of each one of the jobs \(J_{1},J_{2},...,J_{k}\) must be at least as large as the efficiency ratio of \(J^{\prime}\). Let us first handle the case where \(k=1\). If the execution time of \(J^{\prime}\) is totally included within the execution time of \(J_{1}\), job \(J^{\prime}\) receives from \(J_{1}\)  
\[\pi(J_{1})\ \frac{\delta(J^{\prime})}{\delta(J_{1})}\ \geq\ \pi(J^{\prime})\ \frac{\delta(J^{\prime})}{\delta(J^{\prime})}\ =\ \pi(J^{\prime}),\]  
According to Case 1 of the paying scheme. In all other configurations, \(J_{1}\) gives to \(J^{\prime}\) the amount of  
\[\frac{1}{\mu}\ \pi(J_{1})\ \geq\ \frac{1}{\mu}\ (\mu\pi(J^{\prime}))\ =\ \pi(J^{\prime})\]  
By Case 2, and we are done. If \(k>1\), then the same arguments apply to \(J_{1},J_{2},...,J_{k}\). By Lemmas 6 and 7,  
\[\Pi(\text{blue})\leq\left(1+\frac{2}{\mu}\right)\left(\Pi(\text{green})+\Pi( \text{grey})\right).\]Now Lemma 5 allows us to bound all profits by green profits, and we obtain for the profits of OPT and GlobalGreedy  
\[|\mathrm{OPT}| \leq \Pi(\mathrm{green})+\Pi(\mathrm{grey})+\Pi(\mathrm{blue})\] \[\leq 2\ \frac{\mu+1}{\mu(1-\mu)}\ \Pi(\mathrm{green})=2\ \frac{\mu+1}{\mu(1-\mu)}\ | \mathrm{GlobalGreedy}|.\]  
The factor is minimized for \(\mu=\sqrt{2}-1\) to the value \(6+4\sqrt{2}\approx 11.657\). This completes the proof of Theorem 4. The same proof works if the jobs to be scheduled have release times, in addition to duration and completion times. Also, their durations might depend on their actual start times, as long as there are only a polynomial number of changes. We summarize our main result as follows, observing that \(3/2-\sqrt{2}\) is the inverse of \(6+4\sqrt{2}\). **Theorem 8**. : _Let \(U\) be a set of elements, each associated with a real profit, and let \(\mathcal{J}\) be a set of jobs, where each job \(J\) in \(\mathcal{J}\) covers a given subset of universe \(U\), and is given a release time, a completion deadline and a duration. Algorithm GlobalGreedy runs in polynomial time and constructs a feasible schedule whose total profit is at least \(3/2-\sqrt{2}\approx 0.086\) times the maximum possible profit._  
In the geometric firefighter problem, universe \(U\) can be defined as follows. The set \(B\) of allowed barriers consists of a number of straight-line barriers with pairwise disjoint interiors and all endpoints on the boundary of \(P\). We take the arrangement of all barriers of \(B\) inside polygon \(P\), pick a representative point \(u_{c}\) from each cell \(c\), and let the profit of \(u_{c}\) be the area of \(c\); observe that all points in \(c\) share their fates with \(u_{c}\), with respect to the fire. Universe \(U\) equals the set of the points \(u_{c}\) and each barrier \(b\) covers those points \(u_{c}\) whose cells are separated by \(b\) from the fire's starting point. We observe that \(U\) is of size linear in the size of \(B\) since each barrier is placed on the border of at most two cells.