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


Katarzyna Paluch
Simpler approximation of the maximum asymmetric traveling salesman problem

Coauthors: Khaled Elbassioni, Anke van Zuylen


We give a very simple approximation algorithm for the maximum asymmetric traveling salesman problem. The approximation guarantee of our algorithm is 2/3, which matches the best known approximation guarantee by Kaplan, Lewenstein, Shafrir and Sviridenko. Our algorithm is simple to analyze, and contrary to previous approaches, which need an optimal solution to a linear program, our algorithm is combinatorial and only uses maximum weight perfect matching algorithm.


Talk 3 of the invited session Tue.2.H 3021
"Sampling, sorting and graph traversal: Algorithms for finding permutations" [...]
Cluster 2
"Combinatorial optimization" [...]


  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. Since its introduction in the market buying Order 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.