K Centers Problem

Question

You are given n cities and distances between every pair of cities. You have to select k out of n cities where we can place ATMs (warehouses, stores, etc.) such that the maximum distance of a city from the ATM is minimized.
 

Input: 

First line: The number of cities: n

Second line: The distance matrix: dist (n*n matrix).

Third line: The number of ATMs: k
 

Output: 

First line: Maximum distance of a city from the ATM.

Second line: The indexes of selected k cities.
 

Goal: Minimize the maximum distance of a city to an ATM.

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 

Examples:

Consider n = 4, the distance between each city is shown below and k = 2.

Place 2 ATMs in 4 cities, such that the maximum distance of a city to an ATM is minimized.

If we place ATMs in the city 0 and 1, the maximum distance will be  6, but if we place ATMs in any other pair of cities, the maximum distance is at least 7, which is > 6.
 

Output: 6

             0 1

Solution

Recommended: Please try to solve it yourself before moving on to the solution.

This is an NP-hard problem.

Idea: The idea is to use Greedy Approach.

The Greedy algorithm approach selects the best case at each stage until k centers have been chosen. The best case here is to select the city with the largest distance to its nearest center and make it one of the centers to reduce the maximum distance of a city to a center.

Algorithm:

1) Pick the first center at random.

2) Select the remaining k-1 centers as follows:

Let's call the already chosen centers c1, c2, c3,... ci. Choose the (i+1)^th center by selecting the city that is the farthest away from the previously chosen centers, i.e., the point p with the maximum Min(dist(p, c1), dist(p, c2), dist(p, c3), dist(p, c4),.... dist(p, ci)).

Let’s understand by running the algorithm on the above example:

• Initially, we have no centers selected, and hence the distance of all the cities to a center is infinite. 
• Let's select city 0 a center and update all the cities' distances to their closest centers. The city selected as a center has a distance of 0 to the center. 
• Maximum of Minimum of all distanced from all the cities to the city 0: 
  • Max(dist(0, 0), dist(1, 0), dist(2, 0), dist(3, 0)) = max(0, 12, 7, 6) = 6.

• Now the city 1 is at the maximum distance(12) from city 0. Therefore next select city 1 as the center.
• We have two centers selected, and hence the greedy algorithm stops here.
• We got city 0 and city one as our ATM centers, with the maximum distance of a city from ATM being 6(distance of city 2 from city 1).
   

However, this will not work in every case, and we will most likely end up with a close approximation of the ideal result. That's why we call it an Approximate Greedy Algorithm. 

C++

Input: Above Example

Output:

Time Complexity: O(kn) 

Space Complexity: O(n)

Also see, Euclid GCD Algorithm