# Greedy Approximate Algorithm for K Centers Problem in Java

The K Centers Problem is a well-known optimization problem in computer science. Given a set of cities and the distances between them, the problem is to find k cities (called centers) such that the maximum distance between a city and its nearest center is minimized.

Example:

Suppose we have a set of 6 cities, labeled A, B, C, D, E, and F, and the distances between them are as follows:

Our goal is to select 3 centers such that the maximum distance between a city and its nearest center is minimized.

To apply the Greedy Approximate Algorithm, we first select a center at random. Let's say we select city A as the first center. We mark it as selected and initialize the set of centers as follows:

The algorithm then proceeds to select the next center. We compute the distance between each city and the selected center (city A), and select the city farthest from any selected center. In this case, city D has the largest distance of 9, so we select it as the next center. We mark it as selected and update the set of centers as follows:

We repeat this process until we have selected k=3 centers. The algorithm selects city E as the third center, and we end up with the following set of centers:

Finally, we compute the maximum distance to the nearest center for each remaining city. For example, city C has a minimum distance of 4 to the nearest center (city E), so the maximum distance to the nearest center is 4. We compute this distance for all remaining cities and find that the maximum distance is 4.

Therefore, the solution produced by the Greedy Approximate Algorithm in this example is to select cities A, D, and E as centers, with a maximum distance to the nearest center of 4.

## Implementation:

ALGORITHM:

Step 1: Initialize the distance matrix between cities.

Step 2: Initialize a boolean array 'selected' of length n (where n is the number of cities) to all false values

Step 3: Choose a random city i to be the first center

Step 4: Set selected[i] to true and add i to the centers array

Step 5: For each remaining center j from 1 to k-1, do the following:

Step 5.1: Initialize maxDistance to 0 and farthestCity to -1

Step 5.2: For each non-selected city p, do the following:

Step 5.2.1: Initialize minDistance to infinity

Step 5.2.2: For each center q in centers, compute the distance d(p,q)

Step 5.2.3: If d(p,q) < minDistance, set minDistance to d(p,q)

Step 5.2.4: If minDistance > maxDistance, set maxDistance to minDistance and farthestCity to p

Step 5.3: Set selected[farthestCity] to true and add farthestCity to the centers array

Step 6: For each non-selected city p, do the following:

Step 6.1: Initialize minDistance to infinity

Step 6.2: For each center q in centers, compute the distance d(p,q) Step 6.3: If d(p,q) < minDistance, set minDistance to d(p,q)

Step 6.4: If minDistance > maxDistanceToNearestCenter, set maxDistanceToNearestCenter to minDistance

Step 7: Return the centers array and maxDistanceToNearestCenter

FileName: KCentersAlgorithm.java

``````import java.util.Arrays;

public class KCentersAlgorithm {

// Distance matrix between cities
private static int[][] distances = {
{0, 5, 8, 9, 7, 3},
{5, 0, 6, 3, 2, 5},
{8, 6, 0, 4, 8, 4},
{9, 3, 4, 0, 6, 5},
{7, 2, 8, 6, 0, 6},
{3, 5, 4, 5, 6, 0}
};

public static void main(String[] args) {
int k = 3;  // Number of centers to select

// Mark all cities as unselected
boolean[] selected = new boolean[distances.length];
Arrays.fill(selected, false);

// Select a center at random
int currentCenter = (int) (Math.random() * distances.length);
selected[currentCenter] = true;
int[] centers = new int[k];
centers = currentCenter;

// Select remaining centers
for (int i = 1; i < k; i++) {
int maxDistance = 0;
int farthestCity = -1;

// Find the city farthest from any selected center
for (int j = 0; j < distances.length; j++) {
if (!selected[j]) {
int minDistance = Integer.MAX_VALUE;
for (int center : centers) {
int distance = distances[j][center];
if (distance < minDistance) {
minDistance = distance;
}
}
if (minDistance > maxDistance) {
maxDistance = minDistance;
farthestCity = j;
}
}
}

// Mark the farthest city as selected and add it to the set of centers
selected[farthestCity] = true;
centers[i] = farthestCity;
}

// Compute the maximum distance to the nearest center for each remaining city
int maxDistanceToNearestCenter = 0;
for (int i = 0; i < distances.length; i++) {
if (!selected[i]) {
int minDistance = Integer.MAX_VALUE;
for (int center : centers) {
int distance = distances[i][center];
if (distance < minDistance) {
minDistance = distance;
}
}
if (minDistance > maxDistanceToNearestCenter) {
maxDistanceToNearestCenter = minDistance;
}
}
}

// Print the selected centers and the maximum distance to the nearest center
System.out.println("Selected centers:");
for (int center : centers) {
System.out.print((char) ('A' + center) + " ");
}
System.out.println();
System.out.println("Maximum distance to nearest center: " + maxDistanceToNearestCenter);
}
}
``````

Output:

``````Selected centers:A D E
Maximum distance to nearest center: 4
``````

Complexity Analysis:

Time Complexity: O(k * n^2), where n is the number of cities and k is the number of centers to select because for each remaining center, we need to iterate through all the cities to find the farthest city from any selected center. The operation takes O(n^2) time since we need to compute the distance between each pair of cities.

Space Complexity: O(n), where n is the number of cities. We need to store a boolean array to mark which cities have been selected as centers, and an array to store the selected centers. Both of these arrays have a size of n. Additionally, we need to store the distance matrix, which has a size of n^2. However, since the distance matrix is a constant and does not change during the execution of the algorithm, we can consider it to be part of the input and not part of the space complexity.

• The algorithm is easy to implement and computationally efficient.
• The algorithm guarantees a solution that is at most twice as far from optimal, which makes it a good option when the exact solution is not necessary or when a quick approximation is needed.