Module org.jgrapht.core
Package org.jgrapht.alg.centers

Class GonHeuristic<V,E>

java.lang.Object
org.jgrapht.alg.centers.CentersLocationAlgorithmBase<V,E>
org.jgrapht.alg.centers.GonHeuristic<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
CentersLocationAlgorithm<V,E>
public class GonHeuristic<V,E> extends CentersLocationAlgorithmBase<V,E>
The Gon heuristic algorithm for the vertex $k$-center problem.

The vertex $k$-center problem is an NP-hard combinatorial optimization problem that receives a complete edge-weighted undirected graph $G = (V, E, w)$, and a positive integer $k$. The goal is to find a subset $C$ of $V$ such that $|C| = k$ and the maximum distance from any vertex in $V$ to the nearest vertex in $C$ is minimized. $C$ is called the set of centers. The vertex $k$-center problem has applications in clustering and facility location.

The Gon heuristic is a classic heuristic approximation algorithm for the vertex $k$-center problem. It works in a straightforward way. First, a vertex from the input graph is chosen randomly and added to the set of centers $C$. Then, iteratively, the farthest vertex from $V$ to $C$ is chosen and added to $C$. This process is repeated until $|C| = k$. This algorithm provides a guarantee to compute solutions for the vertex $k$-center problem no more than 2-times optimum. According to the literature, this is the best approximation factor (under $P \neq NP$). The implementation chooses the first vertex randomly. Alternatively, an existing set of centers $C$ with fewer than $k$ centers can be provided to be augmented. In this implementation, ties are broken by choosing the vertex with the lowest index.

The description of this algorithm can be consulted on:
T. F. Gonzalez Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 1985, 38, 293-306. J. Garcia-Diaz, R. Menchaca-Mendez, R. Menchaca-Mendez, S. Pomares Hernández, J. C. Pérez-Sansalvador and N. Lakouari, "Approximation Algorithms for the Vertex K-Center Problem: Survey and Experimental Evaluation," in IEEE Access, vol. 7, pp. 109228-109245, 2019, doi: 10.1109/ACCESS.2019.2933875.

This implementation can also be used in order to augment an existing partial set of centers. See constructor GonHeuristic(Set).

The runtime complexity is $O(k*|V|)$.

This algorithm requires that the graph is complete, undirected, and edge-weighted.

Author:
Jose Alejandro Cornejo-Acosta

  • Constructor Details

    • GonHeuristic

      public GonHeuristic(Random rng)
      Constructor. By default the first vertex is chosen randomly.
      Parameters:
      rng - random number generator.

    • GonHeuristic

      public GonHeuristic(Set<V> initialCenters)
      Constructor Specifies a partial set of initial centers that will be augmented to form a set of k centers when getCenters(org.jgrapht.Graph<V, E>, int) is called.
      Parameters:
      initialCenters - Initial set of centers.

  • Method Details