Package org.jgrapht.alg.tour

Class ChristofidesThreeHalvesApproxMetricTSP<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    HamiltonianCycleAlgorithm<V,​E>
    public class ChristofidesThreeHalvesApproxMetricTSP<V,​E>
extends java.lang.Object
implements HamiltonianCycleAlgorithm<V,​E>
    A $3/2$-approximation algorithm for the metric TSP problem.

    The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?". In the metric TSP, the intercity distances satisfy the triangle inequality.

    This is an implementation of the Christofides algorithm. The algorithms is a $3/2$-approximation assuming that the input graph satisfies triangle inequality and all edge weights are nonnegative. The implementation requires the input graph to be undirected and complete. The worst case running time complexity is $\mathcal{O}(V^3E)$.

    The algorithm performs following steps to compute the resulting tour:

    1. Compute a minimum spanning tree in the input graph.
    2. Find vertices with odd degree in the MST.
    3. Compute minimum weight perfect matching in the induced subgraph on odd degree vertices.
    4. Add edges from the minimum weight perfect matching to the MST (forming a pseudograph).
    5. Compute an Eulerian cycle in the obtained pseudograph and form a closed tour in this cycle.

    The following two observations yield the $3/2$ approximation bound:

    • The cost of every minimum spanning tree is less than or equal to the cost of every Hamiltonian cycle since after one edge removal every Hamiltonian cycle becomes a spanning tree
    • Twice the cost of a perfect matching in a graph is less than or equal to the cost of every Hamiltonian cycle. This follows from the fact that after forming a closed tour using the edges of a perfect matching the cost of the edges not from the matching is greater than or equal to the cost of the matching edges.

    For more details, see Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Graduate School of Industrial Administration, Carnegie Mellon University (1976).

    Author:
    Timofey Chudakov, Dimitrios Michail

    • Constructor Detail

      • ChristofidesThreeHalvesApproxMetricTSP

        public ChristofidesThreeHalvesApproxMetricTSP()
        Empty constructor

    • Method Detail

      • getTour

        public GraphPath<V,​E> getTour​(Graph<V,​E> graph)
        Computes a $3/2$-approximate tour.
        Specified by:
        getTour in interface HamiltonianCycleAlgorithm<V,​E>
        Parameters:
        graph - the input graph
        Returns:
        a tour
        Throws:
        java.lang.IllegalArgumentException - if the graph is not undirected
        java.lang.IllegalArgumentException - if the graph is not complete
        java.lang.IllegalArgumentException - if the graph contains no vertices