Towards Better Algorithms for Fundamental Optimization Problems

jakub-tarnawski-photo.jpg
Jakub Tarnawski

Jakub Tarnawski
Doctoral Candidate, Swiss Federal Institute of Technology Lausanne (EPFL)
Monday, February 4, 2019 @ 11:00am-12:00pm
Room 1242, CSE building

 

Abstract:

The constant growth in the sizes of modern datasets, combined with an increasing reliance on algorithms in all areas of life, makes the rigorous study of algorithms more relevant than ever and necessitates the development of new algorithmic techniques. In this talk, I will show how ideas and tools from the theory of polyhedra and linear programming can be applied to make progress in fundamental optimization problems on graphs.

The focus of my talk will be the asymmetric version of the traveling salesman problem (ATSP), which consists in finding the shortest tour that visits all vertices of a given directed graph with weights (costs) on edges. I will show the main ideas that lead to the first constant-factor approximation algorithm for ATSP. In particular, I will explain a generic reduction to structured instances that resemble but are more general than those arising from unweighted graphs. This reduction takes advantage of a laminar family of vertex sets that arises from the standard linear programming relaxation.

I will also briefly discuss a new deterministic parallel algorithm for finding matchings in graphs. The algorithm is obtained by a derandomization of the celebrated Isolation Lemma by Mulmuley, Vazirani and Vazirani in the context of perfect matchings, and its analysis heavily depends on the laminar structure of the faces of the perfect matching polytope.

 

Bio:
Jakub Tarnawski is a doctoral student in the Theory of Computation laboratory at the EPFL, advised by Ola Svensson. He is broadly interested in theoretical computer science and combinatorial optimization, particularly in graph algorithms and approximation algorithms. He is a recipient of the Best Paper Award at STOC 2018 for his work on the traveling salesman problem, and of the Best Paper Award at FOCS 2017 for his work on matchings.

 

Faculty Host: Shachar Lovett