TSP and related problems via Matroids, Matchings and Extensions

Prelegent(ci)

Andras Sebo

Afiliacja

CNRS, Laboratoire G-SCOP, Grenoble

Termin

24 maja 2012 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---