Dimitris N. Chorafas Foundation Award 2019 – Jakub Tarnawski

"For fundamental contributions to theoretical computer science. In particular, for groundbreaking algorithmic progress on two central problems in combinatorial optimization, namely the traveling salesman problem and the matching problem."

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress.

In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A rho-approximation algorithm for ATSP is one that runs in polynomial time and always produces a tour at most rho times longer than the shortest tour. Finding such an algorithm with constant rho had been a long-standing open problem. In this thesis, we give such an algorithm.

In the second part of the thesis we address the perfect matching problem. We have known since the 1980s that it has efficient parallel algorithms if the use of randomness is allowed. However, we do not know if randomness is necessary – that is, whether the matching problem is in the class NC. We show that it is in the class quasi-NC. That is, we give a deterministic parallel algorithm that runs in poly-logarithmic time on quasi-polynomially many processors.