BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:A Unified Analytical Approach to Strongly Polynomial Algorithms fo
 r Structured Linear Programs [Oberseminar Discrete Optimization]
DTSTART:20250708T091500Z
DTEND:20250708T101500Z
DTSTAMP:20260612T202300Z
UID:indico-event-528@math-events.uni-bonn.de
DESCRIPTION:Speakers: Bento Natura (Columbia University)\n\nShortest paths
 \, bipartite matching\, maximum flow\, minimum-cost flow\, generalized flo
 ws\, and discounted Markov decision processes are all central problems in 
 combinatorial optimization. Over the past few decades\, each has inspired 
 the development of sophisticated strongly polynomial-time algorithms\, oft
 en based on tailored methods and distinct algorithmic paradigms.\nIn a sep
 arate line of work\, interior-point methods have been progressively refine
 d to yield faster weakly and strongly polynomial-time algorithms for many 
 of these problems. A recent such algorithm\, introducing the concept of St
 raight Line Complexity (SLC)\, achieves strongly polynomial running time a
 cross all of them.\nIn this talk\, we present a self-contained exposition 
 showing how strong polynomiality can be recovered for several of these pro
 blems through the lens of SLC analysis.\n \nThe Oberseminar takes place i
 n the conference room\, 2nd floor. Participants are invited to have coffee
  or tea in the lounge before.\n \n\nhttps://math-events.uni-bonn.de/event
 /528/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Konferenzraum (Arithmeum / Research
  Institute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/528/
END:VEVENT
END:VCALENDAR