BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:6827afb037c8d
DTSTART;TZID=America/Toronto:20241213T123000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241213T133000
URL:/combinatorics-and-optimization/events/co-reading-g
 roup-rian-neogi-7
SUMMARY:C&O Reading Group - Rian Neogi
CLASS:PUBLIC
DESCRIPTION:Summary \n\nTITLE: A Constant Factor Prophet Inequality for Sub
 additive\nCombinatorial Auctions\n\nSPEAKER:\n Rian Neogi\n\nAFFILIATION:\
 n University of À¶Ý®ÊÓƵ\n\nLOCATION:\n MC 6029\n\nABSTRACT: In this talk\
 , I will go through the paper of Correa and\nCristi that appeared in STOC 
 2023. The paper proves a O(1) prophet\ninequality for online combinatorial
  auctions with subadditive buyers.\n\nTheir techniques involve the use of 
 what they call a Random Score\nGenerator (RSG for short)\, which is a dist
 ribution over prices of the\nitems. Each buyer 'plays' an RSG. The algorit
 hm samples a vector of\nprices of the items from this RSG for each buyer a
 s they arrive\, and\nassigns to them the set of items for which the sample
 d prices are\nlarger than prices from another independent sample from the 
 RSGs of\nall the buyers. A mirroring argument is used to bound the value o
 f the\nallocation computed by their algorithm\, and a novel fixed point\na
 rgument is used to show the existence of RSGs that guarantee a good\nappro
 ximation.\n\nIn contrast to the O(log log m) prophet inequality covered pr
 eviously\nin the CO reading group\, the algorithm in this paper does not r
 un in\npolynomial time\, and does not involve posted prices. \n 
DTSTAMP:20250516T213544Z
END:VEVENT
END:VCALENDAR