Past IGAFIT Colloquia

Follow us on twitter and facebook.



IGAFIT Algorithmic Colloquium #6

December 10, 2020
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
Adrian Vladu, Université de Paris
In recent years, continuous optimization primitives have become an essential component in the algorithmist’s toolkit. Among other developments, this has led to tremendous progress on the quest for developing fast graph algorithms.
In this talk I will give an overview of the techniques based on interior point methods, which have been instrumental to obtaining a set of faster algorithms for fundamental graph problems, which include an m4/3+o(1) log W time algorithm for solving the minimum cost flow problem in graphs with unit capacity.
For sparse graphs, our algorithm improves over the best known running time for this problem and, by well-known reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite b-matching when |b|1 = O(m), and recovers the running time of the recent unit capacity maximum flow algorithm due to Liu-Sidford.

Based on https://arxiv.org/abs/2003.04863
see the video: Colloquium #6

IGAFIT Algorithmic Colloquium #5

November 26, 2020
Fully Online Matching
Zhiyi Huang, University of Hong Kong
Motivated by applications such as ride sharing, we introduce a fully online model of maximum cardinality matching in which all vertices arrive and depart online. On the arrival of a vertex, its edges to previously-arrived vertices are revealed. The vertex can be matched anytime before its departure, which is after all its neighbors’ arrivals. This fully online matching model generalizes the online bipartite matching model which only considers bipartite graphs and assumes one side of the vertices to be offline.

We generalize the Ranking and Water-Filling algorithms to fully online matching and its fractional relaxation respectively. The former is 0.521-competitive in general graphs, and 0.567-competitive in bipartite graphs, and the latter is 0.585 competitive in both cases. Further, we prove that fully online matching is strictly harder than online bipartite matching, because no online algorithm can be 0.6317 <(1-1/e)-competitive in fully online matching even for bipartite graphs. Finally, we introduce new algorithms that are strictly better than Ranking and Water-Filling in fully online matching.
see the video: Colloquium #5

IGAFIT Algorithmic Colloquium #4

November 12, 2020
New Lower and Upper Bounds for quantile summary algorithms
Graham Cormode, University of Warwick
Finding the median, or more generally quantiles, is a core problem in data analysis. The question has been heavily studied in streaming and related models of computation, for over four decades. In this talk I will present some recent advances:
  • Lower bounds for approximating quantiles in the deterministic comparison model, for additive error, which show that the best known algorithm is in fact optimal
  • Upper bounds for relative error epsilon-approximations of quantiles, which improves over previous results and exceed the best known lower bounds by only an O(log(1/ε)3/2) factor.
This covers joint work with Pavel Veselý, Justin Thaler, Edo Liberty and Zohar Karnin.
see the video: Colloquium #4

IGAFIT Algorithmic Colloquium #3

October 29, 2020
A (Slightly) Improved Approximation Algorithm for Metric TSP
Nathan Klein, University of Washington
In this talk, he describes recent work in which he obtains a 3/2-ε approximation algorithm for metric TSP, for some ε>10-36. This slightly improves over the classical 3/2 approximation algorithm due to Christofides [1976] and Serdyukov [1978]. The talk focuses on giving an overview of the key ideas involved. This is joint work with Anna Karlin and Shayan Oveis Gharan
see the video: Colloquium #3

 

IGAFIT Algorithmic Colloquium #2

October 15, 2020
An almost-linear time deterministic algorithm for expander decomposition
Thatchaphol Saranurak, Toyota Technological Institute at Chicago
Expander decomposition is a powerful tool in many areas on graph algorithms (e.g. approximation algorithm, dynamic algorithm, distributed algorithm, property testing, and sketching).
We give a deterministic algorithm for finding this decomposition in almost-linear time. Previous algorithms are either randomized or take quadratic time.
As a consequence, we resolve a major open problem if there is a deterministic dynamic connectivity algorithm with n0.4999 worst-case update time by giving an algorithm with no(1) worst-case update time. The result also implies almost-linear-time deterministic algorithms for approximate max flow, electric flow, and Laplacian solvers.
Joint work with Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, and Richard Peng.
see the video: Colloquium #2

IGAFIT Algorithmic Colloquium #1

October 1, 2020
An improved approximation algorithm for ATSP
Vera Traub, ETH Zürich
In a recent breakthrough, Svensson, Tarnawski, and Végh gave the first constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). In this work we revisit their algorithm. While following their overall framework, we improve on each part of it.
Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. Moreover, we show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio.
Overall, we improve the approximation ratio from 506 to 22 + ε for any ε > 0. We also improve the upper bound on the integrality ratio of the standard LP relaxation from 319 to 22.
This is joint work with Jens Vygen.
see the video: Colloquium #1


Follow us also on twitter and facebook.