BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/40
DTSTAMP:20230914T125907Z
SUMMARY:Online Matchings and Online Advertising
DESCRIPTION:Speaker: Nitish Korula\nDepartment of Computer Science\nUnivers
 ity of Illinois at Urbana-Champaign\n3240\, Siebel Center\n2\n\nAbstract: 
 \nIn a variety of contexts related to Internet advertising\,  online versi
 ons of classic problems such as maximum-weight bipartite  matching arise. 
 With internet advertising becoming a multi-billion  dollar business\, ther
 e is a need for algorithms to solve these  problems effectively. However\,
  without assumptions on the input  distribution\, edge weights\, order of 
 arrival\, etc.\, no online  algorithms for these problems can achieve any 
 bounded competitive ratio.\n\nFortunately\, in many of the advertising con
 texts where these problems  need to be solved\, they do satisfy one or mor
 e of these assumptions.  In this talk\, I will present a collection of alg
 orithms with  competitive ratios ranging from 1/8 to 1-1/e to 1-\\\\epsilo
 n\, solving  problems in ad reservation\, display advertising\, etc. They 
 also have  connections to other well-known problems such as the classical 
  Secretary problem and the Generalized Assignment Problem (GAP). Our  algo
 rithms are simple and efficient\, making online decisions in  essentially 
 linear time (joint work with Martin Pal\, Jon Feldman\, Vahab Mirrokni\, a
 nd S.   Muthu   Muthukrishnan).\n
URL:https://www.tcs.tifr.res.in/web/events/40
DTSTART;VALUE=DATE:20091029
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR