BREAKTHROUGH in Algorithms: Improved Algorithm for Metric TSP,
(Guest Blog by Mohammad Hajiaghayi)
We all recently heard about the breakthrough complexity result by Ryan
Williams on non-uniform circuit lower bounds. Here is a breakthrough from
All of us may heard about the Christofides' algorithm from 1976 for metric
Traveling Salesman Problem (TSP), in which, given an undirected graph G
with nonnegative edge weights on the edges satisfying the triangle
inequality, the goal is find a shortest possible tour that visits each
city once. The algorithm and its analysis is very simple. Create the
minimum spanning tree (MST) T of G, find a minimum weight perfect matching
M (T-join) in the complete graph over the vertices with odd degree in T,
combine the edges of M and T to form an Eulerian circuit and shortcut the
circuit by skipping visited nodes. This simple algorithm is a
3/2-approximation algorithm for metric TSP since both the weight of T and
twice the weight of M are lowerbounds for the optimum. You can write a
natural LP known as Held-Karp relaxation for the problem, for which one
can show an integrality gap of at most 3/2 essentially via Christofides'
algorithm. For lowerbounds, we know that the integrality gap is at least
4/3 for this LP.
(ADDED BY BILL: According to Wikipedia it is known that you can never get
an approx better than 220/219=1.00456... times opt, unless P = NP.
is the link to the Wikipedia post and
is the paper by Papadrimtriou and Vempala that contains the result.
The post lead me to find it.
Though Christofides' algorithm seems very simple and easy to improve, so
far there has been no progress in this regard despite consistent efforts
from 1976. Today I'm happy to announce a breakthrough for this problem by
Shayan Oveis-Gharan, Amin Saberi and Mohit Singh.
They obtain a (3/2-c)-approximation algorithm, for some positive constant
c, for the graphical TSP where the metric is the shortest path distance in
an unweighted graph (a very natural case considered by many so far). Their
approach is natural also, they find the tour by sampling a random spanning
tree from a maximum entropy distribution defined by the linear programming
relaxation of the problem (similar to the approach of Asadpour, Goemans,
Madry, Oveis-Gharan, and Saberi from SODA'10 on improved algorithms for
asymmetric TSP). Since again the cost of this tree is upper bounded by the
optimum solution, it suffices to show that the cost of its Eulerian
augmentation (or T-join) is
strictly less than half of the optimum. Of course the analysis is not
simple at all. According to the authors:
``The first ingredient of the proof is a deeper study of random spanning
trees and their corresponding generating functions. We build on a
recent and very interesting study of real-stable polynomials and their
applications in discrete probability. In particular, we use these
techniques to bound the probability of events defined on the parity of
the number of edges chosen from a certain subset to be in the random
spanning tree. This is crucial for bounding the cost of the T-join.
The other essential ingredient of our proof is a more detailed
analysis of the near-minimum cuts of the LP solution. We study the
cross graph of (1+d)-near minimum cuts for some d < 1/100 and observe
several interesting properties. In particular, we show that the cross
graph corresponding to these cuts has a structure very similar to
cactuses. Our analysis generalizes to all graphs and it could be of
Amin told me that they should post the paper in arxiv by the end of this month.