*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Tess Malone, Communications Officer
Summary Sentence: Towards Better Algorithms for Fundamental Optimization Problems
Full Summary: No summary paragraph submitted.
Jakub TarnawskiTITLE: Towards Better Algorithms for Fundamental Optimization Problems
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 two of the most 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. Here, our techniques build upon the constant-factor approximation algorithm for the special case of unweighted graphs due to Svensson. 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 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 awards at STOC 2018 for his work on the traveling salesman problem and FOCS 2017 for his work on matchings.
