Hospitals on a road: You are given villages situated along a highway. Let x 1, x 2,
Question:
Hospitals on a road: You are given villages situated along a highway. Let x1, x2,x3 .... xn represent the positions of these villages on the highway (the highway is a straight line). We need to build hospitals in k of these villages. Let di denote the distance from the i-th village to the nearest hospital, and let be the sum of these distances. Our goal is to minimize D.
(a) Give an efficient algorithm to solve the problem fork = 1 and explain why it works. (Hint: Median) (3 pts)
(b) Consider an optimum placement for some k. Prove that thisoptimum
solution can be viewed as consisting of two optimum solutionsfor smaller problems,
where one problem is optimum placement of k - 1hospitals to cover some villages
and the other problem is placing a single hospital to cover therest of the villages.
State the "smaller problems" completely. (4 pts)
(c) Give a polynomial time algorithm to find the smallestpossible value of D
for a given k. (3 pts.)
Introduction To Probability And Statistics
ISBN: 9781133103752
14th Edition
Authors: William Mendenhall, Robert Beaver, Barbara Beaver