There is a long straight country road with expensive houses scattered along it.

Question

There is a long straight country road with expensive houses scattered along it. The houses are owned by affluent stock traders who require cell phone service. You consult for the company that needs to provide the cell service to every house without exception. The towers only have a range of four miles. So you want to place the cell phone towers at locations along the road so that no house is more than four miles from the nearest cell phone tower. You know exact mileage along the road where each house is located. Design a greedy algorithm that will determine the set of locations for the cell towers that requires the fewest cell tower. Denote the location of the i^th house as M_i. Give an efficient algorithm. Specify (pseudo code) an efficient greedy algorithm to achieve this goal with the fewest cell towers. Prove you algorithm always finds the optimal solution. Analyze your algorithms complexity.

Explanation / Answer

Let R be the range of the cell tower, and the house locations , {hk} for k = 1 to n.

Algorithm:

Sort the locations of the house in increasing order, removing any duplicates.
Reset the indices k (and possibly n) to depict this sorted order.
So h1 < h2 < . . . < hn.

if n == 0
return { }

t1 = h1 + R // First tower is at farthest distance.
p = 1 // Index of latest tower.
for k = 2 to n
if abs(hk tp) > R // House hk doesn’t have service.
p = p + 1
tp = hk + R // Build next tower as far down the road as possible.
end
end
return {t1, . . ., tp}

The total complexity here in (n) time

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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