|
|
 |
| |
|
|
|
An Approximate Algorithm for TSP with Four Vertices and Three Lines Inequality |
|
|
|
PP: 41-44 |
|
|
|
Author(s) |
|
|
|
Yon Wang,
|
|
|
|
Abstract |
|
|
| If the distances of TSP satisfy the triangle inequality, the minimum-cost-spanning tree (MST) heuristics produces a tour
whose length is guaranteed to be less than 2 times the optimum tour length and Christofides’ heuristics generates the 3/2 times the
optimum tour length. Otherwise, the quality of the approximation is hard to evaluate. Here a four vertices and three lines inequality is
used to construct an approximation of the optimum tour instead of the triangle inequality. The performance ratio of the heuristics may
not be a constant for all kinds of TSP. But it is determined for a concrete TSP. |
|
|
|
|
|
|
|
