**Tuesday, 14:15 - 14:40 h, Room: H 3010**

**András Sebő**

Shorter tours by nicer ears

**Coauthor: Jens Vygen**

**Abstract:**

I will sketch some ideas leading us to a *7/5*-approximation algorithm for the graphic TSP, a *3/2*-approximation algorithm for the minimum connected *T*-join problem containing the graphic *s-t*-path TSP and a *4/3*-approximation algorithm for the smallest *2*-edge-connected spanning subgraph problem. The key ingredients are:

\begin{compactitem}[-]

a special kind of ear-decomposition using matching theory (theorems of Lovász and Frank).

optimization of the used ear-decomposition using matroid intersection.

minmax theorems of these subjects transformed to linear programming weak duality.

\end{compactitem}

The last make possible to deduce lower bounds for the graphic TSP. These are necessary for proving the approximation ratio and the integrality gap of some associated linear programs.

Talk 3 of the invited session Tue.2.H 3010

**"Travelling salesman problem I"** [...]

Cluster 1

**"Approximation & online algorithms"** [...]