Department of Computer, Control and Management Engineering

+++++++++++++++++++++++++++++++++++

Speaker: Alksander Mądry (EPFL)
Title: Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
Abstract:

We describe a new way of employing electrical flow computations to solve the maximum flow and minimum s-t cut problems. This approach draws on ideas underlying path-following interior-point methods (IPMs) – a powerful tool in convex optimization - and exploits certain interplay between maximum flows and bipartite matchings.

The resulting algorithm provides improvements over some long-standing running time bounds for the maximum flow and minimum s-t cut problems, as well as, the closely related bipartite matching problem. Additionally, we establish a connection between primal-dual structure of electrical flows and convergence behavior of IPMs when applied to flow problems. This connection enables us to overcome the notorious Omega(sqrt(m))-iterations convergence barrier that all the known interior-point methods suffer from.

++++++++++++++++++++++++++

Speaker: Jakub Łącki (Univ. of Warsaw)
Title: Dynamic Steiner Tree  
Abstract:

We study the Steiner tree problem over a dynamic set of terminals. We
consider the model where we are given an n-vertex graph G with
nonnegative edge weights. Our goal is to maintain a tree T which is a
constant approximation of the minimum Steiner tree in G, as the set of
terminal vertices changes over time. The changes applied to the
terminal set are terminal additions or removals. We obtain a
polylogarithmic time algorithm for dynamic Steiner tree in planar
graphs and a sublinear one for general graphs. We also show that after
each operation a small number of changes to the tree (in amortized
sense) suffices to maintain a (2+epsilon)-approximate Steiner tree.
This is joint work with Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski and Anna Zych.

++++++++++++++++++++++

Speaker: Dariusz Leniowski (Univ. of Warsaw)
Title: Online bipartite matching in offline time
Abstract:

We present an alternative method for constructing augmenting-path algorithms and demonstrate it using bipartite matchings. The resulting algorithm is able to maintain maximum cardinality bipartite matching in one-sided online fashion in total time of O(mn^{1/2}), i.e., the same as the offline Hopcroft-Karp algorithm. The resulting procedure is very simple and uses just one graph search algorithm DFS or BFS. Moreover, our approach has a number of desirable properties that, depending on the context, could make it a preferred choice even in the offline setting. Besides introducing the algorithm and the intuition behind it, the talk will outline the major lemmas and sketch the non-technical parts of the proof.

This is joint work with Bartłomiej Bosek, Piotr Sankowski and Anna Zych.