Colloquium on "Circulation Control for Faster Minimum Cost Flow in
Unit-Capacity Graphs" given by Adrian Vladu (Université de Paris). The
seminar will take place at 14:00 CET (local time in central Europe), and
will be followed by a discussion session. We would like to invite you to
take part in the event including the networking session. This new event
aims to integrate the European algorithmic community and keep it connected
during the times of the pandemic. The meeting will be held using Airmeet
platform and to attend please go to
https://www.airmeet.com/e/fbbc79c0-387e-11eb-9b1e-291c38a9ffb4. You can
find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.
We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.
The details of the talk are given below.
December 10, 2020, 14:00 CET
Adrian Vladu (Université de Paris)
Title: Circulation Control for Faster Minimum Cost Flow in Unit-Capacity
Graphs
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 m^{4/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
Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Adi Rosén
Eva Rotenberg
Piotr Sankowski
Christian Sohler
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
