[Colloquium] REMINDER: 2/6 Talks at TTIC: Jakub Tarnawski, EPFL

[Mary Marre via Colloquium]

When:     Wednesday, February 6th at *11:00 am*

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Jakub Tarnawski, EPFL


*Title:      *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 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.

Host: Avrim Blum <avrim at ttic.edu>


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Wed, Jan 30, 2019 at 9:56 PM Mary Marre <mmarre at ttic.edu> wrote:

> When:     Wednesday, February 6th at *11:00 am*
>
> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>
> Who:       Jakub Tarnawski, EPFL
>
>
> *Title:      *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 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.
>
> Host: Avrim Blum <avrim at ttic.edu>
>
>
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190206/e5b01a4a/attachment-0001.html>