SCS Recruiting Seminar: Jakub Tarnawski

Event Details
  • Date/Time:
    • Wednesday January 30, 2019 - Thursday January 31, 2019
      12:00 pm - 12:59 pm
  • Location: MiRC 102 A&B
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:

Tess Malone, Communications Officer


Summary Sentence: Towards Better Algorithms for Fundamental Optimization Problems

Full Summary: No summary paragraph submitted.

  • Jakub Tarnawski Jakub Tarnawski

TITLE: Towards Better Algorithms for Fundamental Optimization Problems


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.



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.

Additional Information

In Campus Calendar

College of Computing, School of Computer Science

Invited Audience
Faculty/Staff, Postdoc, Public, Graduate students, Undergraduate students
No keywords were submitted.
  • Created By: Tess Malone
  • Workflow Status: Published
  • Created On: Jan 23, 2019 - 10:34am
  • Last Updated: Jan 28, 2019 - 3:05pm