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


  •   Online lending company provides a wide range of ways to get money by means of Tennessee Payday Loans. Since its introduction in the market buying Buy Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.