You are not logged in |
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.
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.
