Consider a long, quiet country road with houses scattered very sparsely along it

Question

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). 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 (greedy) algorithm that achieves this goal, using as few base stations as possible. Note: you have to prove that your strategy yields the optimal solution.

Explanation / Answer

Lets assume the houses as n points H={H1, . . . , Hn} on a line in the order from left to right, and take the base stations as some other k points P1, . . . , Pk on the same line. A solution is feasible iff every point Hi is within 4 miles of some point Pj. The greedy strategy is to place P1exactly four miles to the right of H1, remove all houses covered by P1, i.e. within 4 miles of P1, and then solve the sub-problem consisting remaining houses repeatedly. Let’s call the rest of the houses as H. Let P= (P1, . . . , Pk) be the solution given by our algorithm. We will prove by induction that our solution is optimal. The base case is trivial. Suppose our algorithm is correct for any set of atmost n-1 houses. Consider n houses H1, . . . , Hn.
Case 1:there exists an optimal solution O which place a base station at P1.

Proof. Let O={P1, . . . Pm} be any optimal solution. Obviously P1 cannot be to the right of P1, or else H1 is not covered. Therefore the set of houses P1 (all houses within 8miles to the right of H1)contains the set of houses P1 covers. Consequently, O={P1, P2, . . . , Pm} is a feasible solution which is optimal because it has as many base stations as O.
Case 2: let O={P1, P2, . . . Pm} be an optimal solution which consists of P1, then O={P2, . . . , Pm} is optimal for the sub-problem H containing houses that P1does not cover.
Proof.If a better solution exists to the sub-problem H, then that solution along with P1would be feasible (all of H are covered) and would be better than O, violating the optimality of O.
Conclusion: The cost of our solution is1 + (k-1) = 1 +OPT(H) = 1 +cost(O) =cost(O) =OPT(H).The first equality follows from the induction hypothesis that our algorithm is optimal for H. The second equality follows from Case 2. The third follows from the definition of O in Case 2. If the Hi are already in sorted form, the algorithm runs in time O(n). If not then O(nlogn)is needed.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.