Package com.jgalgo.alg.shortestpath

Class TspMetricMatchingAppx

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 Details

TspMetricMatchingAppx

public TspMetricMatchingAppx()

Create a new TSP \(3/2\)-approximation algorithm.