BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:10th Colloquium of the Research Area C3 [C3 Kolloquium / Colloquiu
 m of the Research Area C3]
DTSTART:20250221T080000Z
DTEND:20250221T100000Z
DTSTAMP:20260415T095700Z
UID:indico-event-142@math-events.uni-bonn.de
DESCRIPTION:Speakers: Sharat Ibrahimpur (University of Bonn)\, László V
 égh (University of Bonn)\n\n\n\n\n\n\n\n\n\n\n09:30\n\n\n\n\nCoffee and T
 ea \n10:00\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nLászló Végh: From Incre
 mental Transitive Cover to Strongly Polynomial Maximum Flow\n10:45\n\n\n\n
 \n\n\n\n\n\n\n\n\n\n\n\n\n\n\nCoffee break\n11:15\n\n\n\n\n\n\n\n\n\n\n\n\
 n\n\n\n\n\n\nSharat Ibrahimbur: Stochastic Minimum Norm Combinatorial Opti
 mization\n\n\n\n\n\n\n\n\n\n \nAbstracts\nLászló Végh:From Incremental
  Transitive Cover to Strongly Polynomial Maximum FlowWe provide faster str
 ongly polynomial time algorithms solving maximum flow in structured n-node
  m-arc networks. Our results imply an an n^{omega + o(1)}-time strongly po
 lynomial time algorithms for computing a maximum bipartite b-matching wher
 e omega<2.38 is the matrix multiplication constant. Additionally\, they im
 ply an (m^{1 + o(1)} W)-time algorithm for solving the problem on graphs w
 ith a given tree decomposition of width W. We obtain these results by str
 engthening and efficiently implementing an approach in Orlin's state-of-th
 e-art O(mn) time maximum flow algorithm from 2013. We develop a general fr
 amework that reduces solving maximum flow with arbitrary capacities to (1)
  solving a sequence of maximum flow problems with polynomial bounded capac
 ities and (2) dynamically maintaining a size-bounded supersets of the tran
 sitive closure under edge additions\; we call this incremental transitive 
 cover. Our applications follow by leveraging recent weakly polynomial\, al
 most linear time algorithms for maximum flow due to Chen et al. (2022) and
  van den Brand et al. (2013)\, and by developing new incremental transitiv
 e cover data structures for special cases.This is joint work with Daniel D
 adush\, James Orlin\, and Aaron Sidford.Sharat Ibrahimpur:Stochastic Minim
 um Norm Combinatorial OptimizationIn this work\, we introduce and study st
 ochastic minimum-norm optimization. We have an underlying combinatorial op
 timization problem where the costs involved are random variables with give
 n distributions\; each feasible solution induces a random multidimensional
  cost vector. We seek a solution that minimizes the expected norm of the i
 nduced cost vector\, for a given monotone\, symmetric norm. We give a gen
 eral framework for devising approximation algorithms for stochastic minimu
 m-norm optimization\, using which we obtain approximation algorithms for t
 he stochastic minimum-norm versions of the load balancing and spanning tre
 e problems.Based on joint work with Chaitanya Swamy.\nWebsite: https://www
 .mathematics.uni-bonn.de/hcm/events/colloquia_c3/coll_10\nResearch Area: 
 C3 Combinatorial optimization\, complexity\, and chip design\nColloquium h
 istory: https://www.or.uni-bonn.de/hausdorff.html\n\nhttps://math-events.u
 ni-bonn.de/event/142/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/142/
END:VEVENT
END:VCALENDAR