BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20131027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20140330T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.6767.field_data.0@www.diag.uniroma1.it
DTSTAMP:20210730T061734Z
CREATED:20131113T225028Z
DESCRIPTION:+++++++++++++++++++++++++++++++++++Speaker: Alksander Mądry (EP
FL)Title: Navigating Central Path with Electrical Flows: from Flows to Mat
chings\, and BackAbstract:We describe a new way of employing electrical fl
ow computations to solve the maximum flow and minimum s-t cut problems. Th
is approach draws on ideas underlying path-following interior-point method
s (IPMs) – a powerful tool in convex optimization - and exploits certain i
nterplay between maximum flows and bipartite matchings.The resulting algor
ithm 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 connecti
on between primal-dual structure of electrical flows and convergence behav
ior of IPMs when applied to flow problems. This connection enables us to o
vercome the notorious Omega(sqrt(m))-iterations convergence barrier that a
ll the known interior-point methods suffer from.++++++++++++++++++++++++++
Speaker: Jakub Łącki (Univ. of Warsaw)Title: Dynamic Steiner Tree Abstrac
t:We study the Steiner tree problem over a dynamic set of terminals. Wecon
sider the model where we are given an n-vertex graph G withnonnegative edg
e weights. Our goal is to maintain a tree T which is aconstant approximati
on of the minimum Steiner tree in G\, as the set ofterminal vertices chang
es over time. The changes applied to theterminal set are terminal addition
s or removals. We obtain apolylogarithmic time algorithm for dynamic Stein
er tree in planargraphs and a sublinear one for general graphs. We also sh
ow that aftereach operation a small number of changes to the tree (in amor
tizedsense) suffices to maintain a (2+epsilon)-approximate Steiner tree.Th
is is joint work with Jakub Oćwieja\, Marcin Pilipczuk\, Piotr Sankowski a
nd Anna Zych.++++++++++++++++++++++Speaker: Dariusz Leniowski (Univ. of Wa
rsaw)Title: Online bipartite matching in offline timeAbstract:We present a
n alternative method for constructing augmenting-path algorithms and demon
strate it using bipartite matchings. The resulting algorithm is able to ma
intain 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-Kar
p algorithm. The resulting procedure is very simple and uses just one grap
h search algorithm DFS or BFS. Moreover\, our approach has a number of des
irable properties that\, depending on the context\, could make it a prefer
red choice even in the offline setting. Besides introducing the algorithm
and the intuition behind it\, the talk will outline the major lemmas and s
ketch the non-technical parts of the proof.This is joint work with Bartłom
iej Bosek\, Piotr Sankowski and Anna Zych.
DTSTART;TZID=Europe/Paris:20131120T110000
DTEND;TZID=Europe/Paris:20131120T110000
LAST-MODIFIED:20131119T100625Z
LOCATION:DIAG - Via Ariosto 25\, Room A2\, 11:00 - 13:00
SUMMARY:Seminars on Graph Algorithms: Alksander Mądry (EPFL) \, Jakub Łącki
(Univ. of Warsaw)\, Dariusz Leniowski (Univ. of Warsaw) - Alksander Mąd
ry (EPFL) \, Jakub Łącki (Univ. of Warsaw)\, Dariusz Leniowski (Univ. of
Warsaw)
URL;TYPE=URI:https://www.diag.uniroma1.it/node/6767
END:VEVENT
END:VCALENDAR