# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 4 An Approximation Algorithm for the Geometric Firefighter Problem
**while** there is still any unconsidered job \(\mathbf{do}\)  
Consider an unconsidered job \(J\) which maximizes the ratio of the total profit of the red elements it covers, divided by its duration. Insert \(J\) into schedule \(L\) if and only if this can be done respecting the deadline for \(J\) and without any re-scheduling of other jobs, except for possibly deleting consecutive jobs in \(L\) whose property profits are altogether not greater than \(\mu\) times the total profit of all red elements covered by \(J\). (In case there are several options for when to schedule \(J\) satisfying this condition, choose one of them arbitrarily.) If \(J\) is inserted, change to green the colour of all red elements covered by \(J\). For each job \(J^{\prime}\) deleted from schedule \(L\), change from green to grey the property elements of \(J^{\prime}\). **Theorem 4**: _The above algorithm GlobalGreedy runs in polynomial time and achieves an approximation factor of \(\approx\)11.65 if parameter \(\mu\) is set to \(\sqrt{2}-1\approx 0.41\)._  
We will need the following lemma. For ease of reference, let us denote by \(\Pi(\text{green})\) the total profit of all green elements in \(U\), at a given time, and similarly for the other colours. **Lemma 5**: _At each time, we have_  
\[\Pi(\text{grey})\ \leq\ \frac{\mu}{1-\mu}\Pi(\text{green}).\]  
By induction on the number of job insertions with deletions. Before the first job is deleted from the schedule \(L\), there are no grey elements, and the lemma holds. Suppose that, upon inserting job \(J\), jobs with a total green profit of \(z\) are deleted from \(L\). All this green profit turns grey. But, by definition of GlobalGreedy, job \(J\) wins at least \(z/\mu\) new green profit, so that  
\[\frac{\mu}{1-\mu}\Pi(\text{green})^{\prime}\ -\ \Pi(\text{grey})^{\prime} \geq \frac{\mu}{1-\mu}(\Pi(\text{green})-z+\frac{z}{\mu})\ -\ (\Pi(\text{grey})\ +\ z)\] \[= \frac{\mu}{1-\mu}\Pi(\text{green})\ -\ \Pi(\text{grey})\ \geq\ 0.\]  
Let us run algorithm GlobalGreedy. All jobs in the final schedule are called green, and those jobs that were inserted into \(L\) and later removed, grey. Now let us define OPT to be any specific schedule achieving maximum profit. We change to blue the colour of all elements still red that are covered by OPT (noting that no green or grey elements become blue). Such a blue element is assigned, as a blue property element, to the first job \(J\) in OPTthat covers it. Job \(J\) cannot be green or grey, because then it would no longer cover red elements. Consequently, if we name such a job \(J\) blue, the three colour classes are pairwise disjoint. In order to prove Theorem 4 we are using a paying scheme, where each green or grey job \(J\) pays money to any blue job \(J^{\prime}\) performed at least partially during the same time as \(J\) (note that every job ever inserted into \(L\) is assigned a unique execution time that will never be altered by GlobalGreedy). The paying scheme is specified as follows. The Paying Scheme. Case 1: The execution time of \(J^{\prime}\) is totally included within the execution time of \(J\). In this case, \(J\) gives to \(J^{\prime}\) money equal to the property profit of \(J\), times the ratio of the duration of \(J^{\prime}\) divided by the duration of \(J\). Case 2: In all other cases where the execution intervals of \(J\) and \(J^{\prime}\) overlap, \(J\) gives to \(J^{\prime}\) money equal to \(1/\mu\) times the property profit of \(J\). **Lemma 6**. : _A green or grey job \(J\) pays at most \(1+2/\mu\) times its property profit to blue jobs._  
Proof. : \(J\) pays \(1/\mu\) times its property profit to at most two blue job whose execution intervals include the start or end time of \(J\). In addition, \(J\) pays money to blue jobs whose scheduled times are totally included within the execution interval of \(J\), in linear proportion to their respective duration; together, these payments do not exceed the property profit of \(J\). The following lemma shows that each blue job is well-paid by this scheme. **Lemma 7**.