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" [...]

     

  •   There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.