CATS-Jan-21-2015
Title
Maximum ATSP with Weights Zero and One via Half-Edges
Speaker
Katarzyna Paluch
Abstract
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight.
In this paper we give a fast combinatorial 3/4-approximation algorithm for Max ATSP. It is based on a novel technique of eliminating problematic subgraphs with the aid of half-edges and a new method of edge coloring. (A half-edge of edge (u,v) is informally speaking ``either a head or a tail of (u,v).)
The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of 2/3, are due to Kaplan, Lewenstein, Shafrir, Sviridenko (2003) and Elbassioni, Paluch, van Zuylen (2012). Using a recent result by Mucha (2013), we obtain also a 2 11/30 ~ 2,3667-approximation algorithm for the shortest superstring problem (SSP), beating the previously best known (having approximation factor equal to 2,4782.)