The Salesman’s Improved Paths
András Sebő
CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
2016/05/04 Wed 4PM-5PM
A new algorithm will be presented for the path tsp, with an improved analysis and ratio. After the starting idea of deleting some edges of Christofides’ trees, we do parity correction and eventual reconnection, taking the salesman to travel through a linear program determining the conditional probabilities for some of his choices; through matroid partition of a set of different matroids for a better choice of his initial spanning trees; and through some other adventures and misadventures.
The proofs proceed by global and intuitively justified steps, where the trees do not hide the forests.
One more pleasant piece of news is that we get closer to the conjectured approximation ratio of 3/2, and a hopefully last misadventure before finishing up this problem is that we still have to add 1/34 to this ratio, and also for the integrality gap. (The previous result was 8/5 with slight improvements.)
This is joint work with Anke van Zuylen.
The proofs proceed by global and intuitively justified steps, where the trees do not hide the forests.
One more pleasant piece of news is that we get closer to the conjectured approximation ratio of 3/2, and a hopefully last misadventure before finishing up this problem is that we still have to add 1/34 to this ratio, and also for the integrality gap. (The previous result was 8/5 with slight improvements.)
This is joint work with Anke van Zuylen.
Tags: AndrasSebo