TSP and related problems via Matroids, Matchings and Extensions

Speaker(s)

Andras Sebo

Affiliation

CNRS, Laboratoire G-SCOP, Grenoble

Date

May 24, 2012, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

I present  improved approximation guarantees for the graphic TSP and some related problems.

For the graphic TSP itself, the new approximation ratio is $7/5$. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio $3/2$. This contains the graphic $s$-$t$-path-TSP as a special case.  Our improved approximation guarantee for finding a smallest $2$-edge-connected spanning subgraph is $4/3$.

The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs, a particular matroid intersection problem.  Matchings, Joins, Matroids are the key-words of this approach. I would like to communicate the intuition that leads from these classical notions to the new approximation results.

These are common results with Jens Vygen.

---