Constant Factor Approximation for ATSP with Two Edge Weights We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called LocalConnectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve LocalConnectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the HeldKarp relaxation, which may be of independent interest.

A Supernodal AllPairs Shortest Path Algorithm We show how to exploit graph sparsity in the FW algorithm for the allpairs shortest path (APSP) problem. FW is an attractive choice for APSP on highperforming systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, FW will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between FW and Gaussian elimination, and thereby import several algorithmic techniques from sparse Cholesky factorization, namely, fillin reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality, and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than a baseline FW that does not exploit sparsity. Our experiments suggest that FW algorithm can be competitive with Dijkstraxe2x80x99s algorithm (the algorithmic core of Johnsonxe2x80x99s algorithm) for several classes sparse graphs.Npiyush kumar saoOak Ridge National LabRamki KannanOak Ridge National LaboratoryPras