BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1635
DTSTAMP:20251119T062441Z
SUMMARY:Approximation Algorithms for Optimization under Uncertainty
DESCRIPTION:Speaker: Sharat Ibrahimpur (ETH Zurich)\n\nAbstract: \nUncertai
 nty is ubiquitous in real-world problems\, highlighting a growing need for
  new mathematical and algorithmic tools for optimization under uncertainty
 . In this talk\, I will discuss two prominent hurdles that arise in stocha
 stic combinatorial optimization\, along with recent advances that address 
 these challenges. \nThe first setting considers a generic combinatorial o
 ptimization problem in which the costs are random variables with known dis
 tributions\, and feasible solutions induce multi-dimensional cost vectors.
  The algorithmic goal is to compute an oblivious solution that minimizes t
 he expected norm of the associated cost vector for a given monotone\, symm
 etric norm. One can show that optimizing the norm of the expected cost vec
 tor may yield solutions whose approximation quality degrades with the dime
 nsionality of the problem. I will present a powerful theorem\, dubbed appr
 oximate stochastic majorization\, that enables constant-factor approximati
 ons for norm-based objectives across a wide class of combinatorial optimiz
 ation problems. \nI will then turn to stochastic decision environments wh
 ere forgoing adaptivity for simplicity or analytical convenience can lead 
 to poor approximation guarantees. I will illustrate this through a novel v
 ariant of two-stage stochastic load balancing that enables a quantitative 
 trade-off between the practical benefits of non-adaptive algorithms and th
 eir performance limitations. I will present a striking power-of-two-choice
 s result for stochastic load balancing\, showing that constant-factor appr
 oximations are achievable with limited adaptivity relative to the omniscie
 nt and adaptive optimums. \nShort Bio:Sharat Ibrahimpur is a postdoctoral
  researcher in the Computer Science department at ETH Zurich. Previously\,
  he held postdoctoral positions at the University of Bonn and the London S
 chool of Economics. Sharat earned his M.Math. and Ph.D. degrees in Combina
 torics and Optimization from the University of Waterloo. He completed his 
 undergraduate degree in Applied Mathematics at the Indian Institute of Tec
 hnology Roorkee. Sharat's research focuses on designing approximation algo
 rithms for combinatorial optimization problems\, with a special emphasis o
 n optimization under uncertainty. \n
URL:https://www.tcs.tifr.res.in/web/events/1635
DTSTART;TZID=Asia/Kolkata:20251204T113000
DTEND;TZID=Asia/Kolkata:20251204T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR