BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1542
DTSTAMP:20250411T052318Z
SUMMARY:Some problems related to online bipartite matching
DESCRIPTION:Speaker: Arghya Chakraborty (TIFR)\n\nAbstract: \nSeveral real-
 world problems work in the 'online' setting where the input arrives in a s
 equential manner and decisions\, sometimes irrevocable\, need to be taken 
 without access to the future inputs. In this thesis\, we work on the onlin
 e version of two problems: bipartite matching and facility location. In th
 is synopsis\, I'll present some of the results we obtained while studying 
 the online bipartite matching problem.\n \nThe online bipartite matching 
 problem is one of most classical online algorithms studied. Several real-l
 ife problems like organ donation\, ad allocation etc can be formulated in 
 terms of online bipartite matching. In their seminal work\, Karp\, Vaziran
 i and Vazirani introduced the RANKING algorithm\, a randomized algorithm w
 hich attained a competitive ratio of (1-1/e) for the unweighted case and s
 howed that no randomized algorithm can do better. It is also known that th
 e WATERLEVEL algorithm attains a similar competitive ratio for the determi
 nistic fractional version of the unweighted  problem. A lot of work has g
 one recently towards extending these algorithms to edge-weighted settings.
  In particular\, a new sub-routine called online correlated selection (OCS
 ) was introduced to achieve competitive ratio beyond the trivial 1/2 obtai
 ned by the greedy algorithm\n \nIn this work\, we present the following r
 esults related to the online bipartite matching problem\nWe show that for 
 the degree-2 bounded case\, where every online vertex has degree at most t
 wo\, the folklore half-half algorithm achieves a competitive ratio of  0.
 717772 and more surprisingly show that this is in fact tight\, no randomiz
 ed algorithm can do any better\nWe give a new OCS subroutine which attains
  the optimal parameter of 1/4. Previous results had shown that no OCS subr
 outine (even in the fully offline setting) can achieve a parameter better 
 than 1/4.\nWe give a deterministic WATERLEVEL-based algorithm that achieve
 s a competitive ratio of (1-1/e) for the edge-weighted case. This result w
 as known before\, but to the best of our knowledge\, this presentation in 
 terms of water-level is new.\nIn the talk\, I'll describe the bipartite ma
 tching problem\, OCS problem\, a summary of known results and an overview 
 of the new algorithms that prove the above stated results.\n
URL:https://www.tcs.tifr.res.in/web/events/1542
DTSTART;TZID=Asia/Kolkata:20250411T153000
DTEND;TZID=Asia/Kolkata:20250411T163000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR