Class ChristofidesThreeHalvesApproxMetricTSP<V,E>
 java.lang.Object

 org.jgrapht.alg.tour.ChristofidesThreeHalvesApproxMetricTSP<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,E>
public class ChristofidesThreeHalvesApproxMetricTSP<V,E> extends 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:
 Compute a minimum spanning tree in the input graph.
 Find vertices with odd degree in the MST.
 Compute minimum weight perfect matching in the induced subgraph on odd degree vertices.
 Add edges from the minimum weight perfect matching to the MST (forming a pseudograph).
 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.: Worstcase 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 Summary
Constructors Constructor Description ChristofidesThreeHalvesApproxMetricTSP()
Empty constructor

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description GraphPath<V,E>
getTour(Graph<V,E> graph)
Computes a $3/2$approximate tour.



Method Detail

getTour
public GraphPath<V,E> getTour(Graph<V,E> graph)
Computes a $3/2$approximate tour. Specified by:
getTour
in interfaceHamiltonianCycleAlgorithm<V,E>
 Parameters:
graph
 the input graph Returns:
 a tour
 Throws:
IllegalArgumentException
 if the graph is not undirectedIllegalArgumentException
 if the graph is not completeIllegalArgumentException
 if the graph contains no vertices

