1. That algorithm starts by choosing a supplier that is closest to an arbitrary customer, then in each of the following iterations it chooses the supplier that is closest to the furthest customer from the currently selected suppliers.
Claim: The above algorithm is 3-approximation algorithm for the k-suppliers problem.
Proof: Consider the k groups of customers induced by an optimal solution with its corresponded suppliers . Now suppose that the algorithm chooses a customer from each of these groups, and its corresponded suppliers , let be a customer in the th group, then from the triangle inequality it follows that:
where is the value of an optimal solution.
On the other hand, if the algorithm chooses 2 customers from the same group, and let be a customer in the th () group, then it follows that:
2. To show that there is no -approximation algorithm for unless P = NP consider an instance of the set cover problem and consider the metric space and , then for and there are k suppliers with distance 1 from D there is a set cover of size k.