Speaker: Moshe Lewenstein (BIU)

Title: Approximating Maximum TSP using Edge Colorings

Abstract:
---------
The {\em asymmetric maximum travelling salesman} problem, also known as
the Taxicab Ripoff problem, is the problem of finding a maximally weighted
tour in a complete asymmetric graph with non-negative weights. Interesting
in its own right, this problem is also motivated by such problems such as
the {\em shortest superstring} problem. We propose a polynomial time
approximation algorithm for the problem with a ${5 \over 8}$ approximation
guarantee. 

The crux of the algorithm is an LP-rounding based on edge coloings of
bipartite multigraphs. 

I will not assume prior knowledge of approximation algorithms. 

joint work with Maxim Sviridenko