1.
Question
1.1.
Examples:
2.
Solution
2.1.
Idea: The idea is to use Greedy Approach.
2.2.
Algorithm:
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# K Centers Problem

GAZAL ARORA
0 upvote

## 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

## FAQs

1. What is meant by the approximation algorithm?
An approximation algorithm is a way of solving with NP-completeness for an optimization problem. The goal of the approximation algorithm is to approach the optimal solution as closely as possible in polynomial time.

2. What do you mean by p, np, or decision problem?
A decision problem is a problem that has a yes or no answer.
P is a class of problems that contains all the decision problems that can be solved in a polynomial time.
NP is a class of problems that contains all decision problems with proofs that can be verified in polynomial time for situations where the answer is "yes."

3. What do you mean by NP-hard problem?
These problems are at least as difficult as NP-complete problems. NP-hard problems don't have to be in NP or be decision problems.

## Key Takeaways

This article solved an NP-hard problem using an Approximate Greedy Algorithm. The algorithm runs in O(kn) time where k is the no. of ATM centers, and n is the number of cities.