BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20261025T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260424T033726Z
UID:69e607832afef828804679@ist.ac.at
DTSTART:20260423T113000
DTEND:20260423T123000
DESCRIPTION:Speaker: Gramoz Goranci\nAbstract: Cut-based graph problems are
  central to combinatorial optimization and theoretical computer science. A
  powerful algorithmic framework for tackling these problems is cut-based t
 ree embedding\, where the goal is to compute a collections of trees that a
 pproximately preserves the values of all cuts in any given graph. The semi
 nal work of Rcke (2008)\, in the context of oblivious routing\, showed how
  to construct such trees with near-optimal quality O(log n). Building on t
 his\, Madry (2010) introduced j-tree embeddings to accelerate Rckes constr
 uction at the cost of a slightly worse approximation guarantee. These resu
 lts have been instrumental in the development of near-optimal algorithms f
 or approximating undirected maximum flow.More recently\, the focus has shi
 fted to the dynamic setting\, where the challenge is to maintain these emb
 eddings as the underlying graph undergoes edge insertions and deletions. S
 trikingly\, techniques developed for dynamic j-tree embeddings have also b
 ecome a key ingredient in the recent breakthrough static algorithm for com
 puting maximum flow in directed graphs.In this talk\, I will present the a
 lgorithmic constructions underlying static\, cut-based tree and j-tree emb
 eddings. Time permitting\, I will also discuss some of our recent work on 
 dynamic variants of these objects and their algorithmic applications.This 
 is based both on prior work by others and on my joint work with Li Chen\, 
 Monika Henzinger\, Peter Kiss\, Ali Momeni\, Richard Peng\, Thatchaphol Sa
 ranurak\, and Gernot Zcklein.
LOCATION:Moonstone Bldg / Ground floor / Seminar Room G (I24.EG.030g)\, IST
 A
ORGANIZER:achaturv@ist.ac.at
SUMMARY:Gramoz Goranci: TCS Seminar - Static and Dynamic Cut-Based Tree Emb
 eddings
URL:https://talks-calendar.ista.ac.at/events/6424
END:VEVENT
END:VCALENDAR