Let’s consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let’s suppose that despite the bucolic setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations. Give an efficient algorithm that achieves this goal, using as few base stations as possible. Suppose you are given this algorithm: start at the western end of the road and begin moving east until the first moment when there is a house h exactly four miles to the west. Place a base station at this point (if you go any further east without placing a base station, you would not cover h). Then delete all the houses covered by this base station and iterate this process on the remaining houses.

Solution Sketch. Think of the houses as olos H = {Hi,..., HnI on a line in that order from left to right, and the hose stations as some other k points Ph• • • , Pk on the some line. A solution is feasible iff every point Hi is within 4 miles of some point Pi. Our greedy strategy is to put Pt exactly four miles to the right of HI, remove all houses covered by Pr, i.e. within 4 miles of Pr, and then recursively solve the sub-problem containing the rest of the houses. Let's refer to the rest of the houses as Let P = (P1,• • • , Pk) be the solution returned by our algorithm We will show by induction on o that our solution is optimal The base case is trivial Suppose our algorithm is correct for any set of at most n— I homes. Consider n houses Hi H„. Claim I: there exists an optimal solution 0 which puts a base station at Pr. Proof Let = (Pr • • • PLI be any optimal solution. Clearly P; cannot be to the right of Pr, or else Hi is not covered. Thus, the set of homes Pt covers (all houses within 8 miles to the right of Hi) contains the set of houses 11 covers. Consequently, 0 = {PI,P2,• • • , P:„} is a feasible solution which is optimal since it has as many base stations as 0'. Claim 2: lot 0 = P2, • • • P:d be an optimal solution which contains Pr, then 0' = {P2, • • • , P:„} is optimal for the sub-problem 7€ containing houses that Pt does not cover. Proof If there is a bettor solution to the sub-problem H', then that solution along with Pt would be feasible (all of 'Ham are covered) and would be bettor than 0, violating the optimality 010. Conclusion. The cost of our solution is I + (k — I) = I -I- OPT(W) = I + c.1(0') = cost(0) = oter(H). The first equality follows from the induction hypothesis that our algorithm is optimal for ie. The second equality follows from Claim 2 The third follows from the definition of CY in Claim 2 If the Hi are already sorted, the algorithm ruin in time 0(o). If not, 0(alg n) is needed.

Explanation: