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.ugov-ricerca.uniroma1.it
DTSTAMP:20260407T183628Z
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:http://www.ugov-ricerca.uniroma1.it/node/6767
END:VEVENT
END:VCALENDAR