BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1757
DTSTAMP:20260805T093507Z
SUMMARY:Online Bipartite Matching and Facility Location.
DESCRIPTION:Speaker: Arghya Chakraborty (TIFR Mumbai)\n\nAbstract: \n\nMany
  optimization problems arise in an online setting\, where inputs arrive se
 quentially and decisions must be made without knowledge of the future. Thi
 s thesis studies two fundamental online optimization problems: facility lo
 cation and bipartite matching.\n \nFor online facility location\, we inve
 stigate two natural variants involving weighted requests and congestion. W
 e present optimal competitive variants for both of these variants.\n \nFo
 r online bipartite matching\, we obtain several new results. We prove that
 \, for degree-2 instances\, the folklore Half-Half algorithm achieves the 
 optimal competitive ratio of approximately 0.7178\, showing that no random
 ized algorithm can do better. We also present a new WaterLevel-based view 
 of optimal deterministic fractional edge-weighted matching\, and analyze a
  candidate online correlated selection algorithm\, obtaining improved guar
 antees over single intervals.\n \nThe talk will present the key ideas beh
 ind these results and the techniques used in their analysis.\n
URL:https://www.tcs.tifr.res.in/web/events/1757
DTSTART;TZID=Asia/Kolkata:20260811T110000
DTEND;TZID=Asia/Kolkata:20260811T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR