$20$:$01$

oll LTE

Sample Final Questions

A Greedy Algorithm for the k$-$Center Problem

A$)$ Apply the given algorithm $($see the flow chart$)$ for the numerical instance that is presented above. Adopt "Manhattan Distance" and solve the problem for $"k=3".(15$ points$).$

If a customer has the same "Manhattan" distance to multiple centers. It is assigned to the center that has the lowest index value.

B$)$ What is the computational complexity of this algorithm for general $"n"($number of customers$)$ and $"m"($number of candidate center locations$)$ and $"k"$ is the number of centers. Explain! $(5$ points$)$