# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 4 An Approximation Algorithm for the Geometric Firefighter Problem  
In this section we present an efficient greedy algorithm for solving the geometric firefighter problem for a finite barrier set \(B\), that achieves a constant approximation factor, where \(B\) consists of disjoint straight-line segments with both endpoints on the boundary of \(P\). Our algorithm works in a more general setting, related to job scheduling and maximum coverage. Each barrier \(b\in B\) of the firefighter problem can be considered a job. It has a duration (the time needed to build it) and a completion time (the last point in time where the fire permits the construction of \(b\) to be completed). Each job is assumed to cover a subset of some finite universe \(U\). The elements of \(U\) carry profits, and a job's profit equals the sum of profits of all elements it covers. The goal is to compute a feasible job schedule whose total profit (i.e., the sum of all profits of jobs scheduled) is maximized. Since this problem generalizes the max-coverage problem, it inherits its inapproximability results. Thus, no approximation factor smaller than \(\approx\)1.5819 can be guaranteed by any polynomial time algorithm, unless \(P=NP\)[7]. (However, this inapproximability result does not necessarily apply to our original firefighter problem). We will now present an approximation algorithm GlobalGreedy that runs in low polynomial time in the size of \(B\) and guarantees an approximation factor of \(\approx\)11.65. After proving this result, we comment more precisely on how this can be applied to the geometric firefighter problem. GlobalGreedy maintains a feasible time schedule \(L\) of jobs, with precise start and completion times for each of the jobs in \(L\). (We may think of the schedule as a list of jobs, sorted according to their scheduled start time, although a more advanced data structure can be employed in order to perform searches and changes of the list more efficiently). The algorithm starts with the empty schedule \(L\). It considers each input job \(J\) exactly once for possible insertion into the schedule \(L\). If \(J\) is rejected, it will never be considered again for inclusion. If \(J\) is scheduled and inserted into the schedule \(L\), its scheduled starting time will never change. However, it may still happen that \(J\) is later deleted from \(L\), in order to make it possible for some other job to be scheduled (partly) during the scheduled time for \(J\). Once \(J\) is deleted, it will never again be considered for insertion into the schedule. Since GlobalGreedy inspects each job only once for possible insertion, the order in which the jobs are considered is crucial. To define this order, and for easier reference in the subsequent proof, we assign colours to all elements of universe \(U\). These colours may change during the process. In the beginning, all elements are coloured red. Each time GlobalGreedy inserts a job \(J\) into the schedule \(L\) the following happens: all red elements covered by \(J\) are irrevocably associated to \(J\), and change colour to green. We will call these elements the _property elements_ of \(J\), and denote by the _property profit_ of \(J\) the total profits of all the property elements of \(J\). Finally, if some job \(J\) is later deleted from the schedule \(L\), in order to make place in the schedule for some other job, then the property elements of \(J\) change colour from green to grey during the deletion of \(J\). GlobalGreedy starts with the empty schedule \(L\), and colours all elements of the universe red. Then it runs the following while-loop, one iteration for every input job \(J\), possibly altering the schedule \(L\), until there are no more jobs left unconsidered. Finally it outputs the schedule \(L\). The order in which the jobs are considered is defined inside the while loop. A parameter \(\mu\in(0,1)\) specifies when jobs will be deleted from the schedule \(L\) in order to accommodate job \(J\) currently under consideration.