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:69cf6b8b18fdb
DTSTART;TZID=America/Toronto:20241213T123000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241213T133000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/co-reading-g
 roup-rian-neogi-7
SUMMARY:C&O Reading Group - Rian Neogi
CLASS:PUBLIC
DESCRIPTION:TITLE: A Constant Factor Prophet Inequality for Subadditive\nCo
 mbinatorial Auctions\n\nSPEAKER:\n Rian Neogi\n\nAFFILIATION:\n University
  of Waterloo\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 pa
 per proves a O(1) prophet\ninequality for online combinatorial auctions wi
 th subadditive buyers.\n\nTheir techniques involve the use of what they ca
 ll a Random Score\nGenerator (RSG for short)\, which is a distribution ove
 r prices of the\nitems. Each buyer 'plays' an RSG. The algorithm samples a
  vector of\nprices of the items from this RSG for each buyer as they arriv
 e\, and\nassigns to them the set of items for which the sampled 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 of the\nalloc
 ation computed by their algorithm\, and a novel fixed point\nargument is u
 sed to show the existence of RSGs that guarantee a good\napproximation.\n\
 nIn contrast to the O(log log m) prophet inequality covered previously\nin
  the CO reading group\, the algorithm in this paper does not run in\npolyn
 omial time\, and does not involve posted prices. 
DTSTAMP:20260403T072603Z
END:VEVENT
END:VCALENDAR