TspMetricMatchingAppx (JGAlgo - Parent 0.5.1-SNAPSHOT API)

java.lang.Object
- com.jgalgo.alg.shortestpath.TspAbstract
- - com.jgalgo.alg.shortestpath.TspMetricMatchingAppx

All Implemented Interfaces:

Tsp
```
public class TspMetricMatchingAppx
extends TspAbstract
```
TSP \(3/2\)-approximation using maximum matching.
The running of this algorithm is \(O(n^3)\) and it achieve \(3/2\)-approximation to the optimal TSP solution.
This algorithm can only accept graphs and weight functions that satisfy the metric condition: every three vertices \(u,v,w\) should satisfy \(d((u,v)) + d((v,w)) \leq d((u,w))$ where \(d(\cdot)\) is the distance of the shortest path between two vertices. This condition is not validated for performance reason, but graphs that do not satisfy this condition will result in an undefined behaviour.
Based on 'Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem' by Nicos Christofides (1976).

Author:

Barak Ugav

- Constructor Summary
  
  Constructors
  Constructor Description
  
  TspMetricMatchingAppx()
  Create a new TSP \(3/2\)-approximation algorithm.
- Method Summary
  - Methods inherited from class com.jgalgo.alg.shortestpath.TspAbstract
    computeShortestTour
  - Methods inherited from class java.lang.Object
    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - TspMetricMatchingAppx
```
public TspMetricMatchingAppx()
```
    Create a new TSP \(3/2\)-approximation algorithm.