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


András Sebő
Shorter tours by nicer ears

Coauthor: Jens Vygen


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:

  • 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.
    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.