K Centers problem in C++

The K Centers problem says that given a number of cities n, select k centers such that the maximum distance of a city from a center is minimized. This problem is a well-known problem that is handled using approximation algorithms. The reason for this is that this problem cannot be solved exactly, which is to say that the correct solution can not be worked out and hence approximation algorithms are used to find an approximation of the optimal solution. Let’s take an example to understand the problem better.

Consider the following weighted graph for n=4 and k=2-

weighted graph

The maximum distance of a city from a center is minimized when the two centers are at cities 0 and 2 with the distance being 5 units.
The distance of a city from a center is the distance between that city and its closest center.

Approach: Greedy Algorithm

The Greedy algorithm approach goes with the best case at every step till we have k centers selected. The best case here means selecting the city that has the maximum distance to its closest center and making it one of the centers so as to minimize the maximum distance of a city to a center. It runs in a loop for k iterations. Let’s go through the previous example and see how greedy algorithm solves it.

At the start, we have no centers selected and hence distance of all the cities to a center is infinite. Hence it makes city 0 a center and updates the distances of all the cities to their closest centers. The city which is selected as a center has distance 0 to a center. Next it selects the city at the maximum distance from city 0, which is city 2. We have 2 centers selected and the hence the greedy algorithm stops here with the maximum distance from a city to a center being 5 and the 2 centers being city 0 and city 2, which is in fact the correct answer. However, this won’t work for every case and we are more likely achieve an approximation of the optimal result. Now that we have understood the approach, let’s take a look at the code.

Code

#include <iostream>
#include <cmath>
#include <bits/stdc++.h> 
#include <vector>
using namespace std;

int maxindex(int * dist,int n){      //function to determine the city with the maximum distance to it's closest center
    int mi=0;
    for(int i=0;i<n;i++){
        if(dist[i]>dist[mi]) mi=i;
    }
    return mi;
}
int main(){
    int n;  //number of cities
    cin>>n; 
    int** weights=new int* [n];
    for(int i=0;i<n;i++){
        weights[i]=new int[n];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j){
                weights[i][j]=0;
            }
            else{
                cin>>weights[i][j];  //Taking input for distances between two cities
            }
        }
    }
    int k;    //Number of centers
    cin>>k;     
    int * dist=new int[n];
    vector <int> centers;
    for(int i=0;i<n;i++){
        dist[i]=INT_MAX;
    }
    int max=0;                       //index of city having the maximum distance to it's closest center
    for(int i=0;i<k;i++){
        centers.push_back(max);
        for(int j=0;j<n;j++){
            dist[j]=min(dist[j],weights[max][j]);  //updating the distance of the cities to their closest centers
        }
        max=maxindex(dist,n);        // updating the index of the city with the maximum distance to it's closest center
    }
    
    cout<<endl<<dist[max]<<endl;     //Printing the maximum distance of a city to a center that is our answer
    
    for(int i=0;i<centers.size();i++){
        cout<<centers[i]<<" ";         //Printing the cities that were chosen to be made centers
    } 
    cout<<endl;
}

 

Input

4
4 8 5
4 10 7
8 10 9
5 7 9
2

Output

5
0 2

 

Time complexity of the code is O(kn) which is the usual time complexity for a greedy algorithm code. It’s O(kn) as the function maxindex() which determines the city with the maximum distance to a center has a time complexity of O(n) and it’s nested inside a loop which runs for k iterations.

Program for Tower of Hanoi using stack in C++

Leave a Reply