A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space

Wenhong Tian, Chaojie Huang, Xinyang WangICORES 2017 · OpenReview

TL;DR

This paper introduces a novel approach for the Traveling Salesman Problem (TSP) by modeling the distribution of optimal tour lengths using a Truncated Generalized Beta (TGB) distribution. This method offers a quality-proved approximation that can approach the true optimum as the number of iterations increases, potentially improving upon the long-standing Christofides algorithm's bound.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP) is a classic NP-hard problem with vast applications across various scientific and engineering fields. For the Symmetric TSP (STSP) with Euclidean distances and satisfying the triangle inequality (often denoted as $\Delta$STSP), the best-known approximation algorithm is Christofides' algorithm, which guarantees a tour length at most 1.5 times the optimal length. However, this 1.5-approximation bound has remained the state-of-the-art for decades, and improving it is a significant open challenge in combinatorial optimization. This paper aims to address this by developing a new approximation strategy that can achieve near-optimal solutions.

Methods

The core of this paper's contribution lies in two main areas:

  1. Generalized Beta (GB) Distribution for Tour Lengths: The authors propose using the Generalized Beta (GB) distribution to model the probability density function (pdf) of optimal tour lengths in $\Delta$STSP. They demonstrate that this distribution fits well with empirical data from random TSPs and TSPLIB instances. The GB distribution has four parameters ($\alpha, \beta, A, B$) that can be determined by matching the first four central moments (mean, variance, skewness, kurtosis) of the observed tour lengths.
  2. Iterative Truncated Generalized Beta (TGB) Approach: Building on the GB distribution, they introduce an iterative algorithm called Truncated Generalized Beta (TGB). This approach starts with the Christofides algorithm (which provides an upper bound of 1.5OPT) and then iteratively refines the solution. In each iteration, the algorithm uses the previous iteration's expected tour length as an upper bound for the current distribution. This process effectively truncates the GB distribution, leading to a quality-proved approximation. The paper derives a theoretical bound for this iterative approach, showing that the approximation ratio approaches $(1 + \frac{1}{2}(\frac{\alpha+1}{\alpha+2})^{K-1})$ as the number of iterations ($K$) increases, where $\alpha$ is a shape parameter of the GB distribution.

Datasets

The paper evaluates its proposed methods using:

  • Random TSP instances: Generated in a unit square with varying numbers of nodes (n=20 to 100, and later n=100 to 500).
  • TSPLIB instances: Standard benchmark instances for TSP, including Burma14.tsp, and others with n ranging from 14 to 52, and up to n=600.

The authors note that the characteristics of random TSPs and TSPLIB instances can differ, and they model the GB distribution for each separately.

Key Insights and Ideas

  • Tour Lengths Follow a Predictable Distribution: A key insight is that the distribution of optimal tour lengths in $\Delta$STSP, even for complex instances, can be effectively modeled by a Generalized Beta distribution. This provides a statistical framework for understanding tour length variability.
  • Iterative Truncation for Improvement: The iterative application of truncation, guided by the GB distribution and starting from a known approximation (Christofides), offers a systematic way to improve the approximation ratio. The theoretical bound suggests that with enough iterations, this method can get arbitrarily close to the optimal solution.
  • Bridging Heuristics and Theory: The TGB approach elegantly combines a well-established heuristic (Christofides) with a probabilistic model (GB distribution) to achieve a theoretically grounded, quality-proved approximation.

Key Results

  • Goodness-of-Fit: The GB distribution demonstrated a good fit for both random TSP instances and TSPLIB instances, as evidenced by high R² values for fitted regression models and visual comparisons with exact distributions.
  • Approximation Accuracy:
    • For random TSPs, the relative error between estimated maxTSPs by GB and LKH results was within 6.5%, with an average below 5%.
  • For medium-sized TSPLIB instances, the relative error was below 7%, with an average below 5%.
  • The iterative TGB algorithm provides a theoretical approximation ratio of $(1 + \frac{1}{2}(\frac{\alpha+1}{\alpha+2})^{K-1})$, which approaches 1 as $K$ increases.
  • Validation: The paper validates its Theorem 1 by showing that the TGB results are consistent with LKH OPT results for TSPLIB instances, with only a few cases showing a few percentage difference.

Limitations and Future Work

  • Computational Complexity: While the TGB algorithm offers theoretical improvements, the paper acknowledges that the Christofides algorithm itself has a computational complexity of O(n³) due to minimum perfect matching. Reducing this complexity for large instances is a direction for future work.
  • Moment Computation: Efficiently computing the third and fourth central moments for large TSP instances remains a challenge.
  • Overestimation: The TGB results are based on the expectation (average) value of the probability distribution, which might overestimate the solution for a given number of iterations.
  • Future Applications: The authors suggest that the closed-form probability density function of the GB distribution opens doors for further applications, such as computing more statistical metrics and analyzing the performance of other approximation algorithms.

Summary updated

Abstract

The traveling salesman problem (TSP) is one of the most challenging NP-hard problems. It has widely applications in various disciplines such as physics, biology, computer science and so forth. The best known approximation algorithm for Symmetric TSP (STSP) whose cost matrix satisfies the triangle inequality (called ?STSP) is Christofides algorithm which was proposed in 1976 and is a 3/2 approximation. Since then no proved improvement is made and improving upon this bound is a funda- mental open question in combinatorial optimization. In this paper, for the first time, we propose Trun- cated Generalized Beta distribution (TGB) for the probability distribution of optimal tour lengths in a TSP. We then introduce an iterative TGB approach to obtain quality-proved near optimal approximation, i.e., (1+1/2((a+1)/(a+2))^(K-1))-approximation where K is the number of iterations in TGB and a(>> 1) is the shape parameters of TGB. The result can approach the true optimum as K increases.
BibTeX
@inproceedings{tian2017near,
  author = {Wenhong Tian and Chaojie Huang and Xinyang Wang},
  title = {{A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space}},
  booktitle = {ICORES},
  year = {2017},
  url = {https://openreview.net/forum?id=OWhwOaO6UY},
}
Figure