A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Svensson
École polytechnique fédérale de Lausanne
January 23, 2018

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.

The Matching Problem in General Graphs is in Quasi-NC

Ola Svensson
École polytechnique fédérale de Lausanne
January 22, 2018

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain a Randomized NC algorithm.