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:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:6a61c69d760cf
DTSTART;TZID=America/Toronto:20260731T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260731T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-kanstantsin-pashkovich-simple-and-almost
SUMMARY:Tutte Colloquium -Kanstantsin Pashkovich-Simple and Almost\nNon-Ada
 ptive 1/2-Approximation for Matroid Prophet Inequalities
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n Kanstantsin Pashkovich\n\nAFFILIATION:\n University 
 of Waterloo\n\nLOCATION:\n MC 5501\n\nABSTRACT: Prophet inequalities are 
 a fundamental model for online\ndecision-making under uncertainty. For mat
 roid constraints\, Kleinberg\nand Weinberg gave a tight 1/2-approximation\
 , but their algorithm uses\nadaptive thresholds that depend on the previou
 sly accepted elements.\nSpecifically\, the mechanism of Kleinberg and Wein
 berg accepts an\narriving element if and only if it is feasible to add wit
 h respect to\nthe matroid constraint and the value of the arriving element
  passes\nits threshold\; but this threshold depends on the elements accept
 ed so\nfar and on the arriving element itself. Later\, Feldman\, Svensson\
 , and\nZenklusen showed that one can give a 1/4-approximation for general\
 nmatroids. Their algorithm is almost non-adaptive\, i.e.\, it uses\nnon-ad
 aptive thresholds but changes the underlying matroid to another\n``stricte
 r'' matroid. Feldman\, Svensson\, and Zenklusen also showed\nthat no const
 ant approximation is possible in general matroids using\nnon-adaptive thre
 sholds if one does not change the underlying matroid.\n\nWe give a new alm
 ost non-adaptive algorithm for matroid prophet\ninequalities that achieves
  a 1/2 guarantee. We change the underlying\nmatroid to a ``stricter'' new 
 matroid that is a direct sum of several\nmatroids. For each part of the ne
 w matroid\, we precompute a single\nnon-adaptive threshold. Once the eleme
 nts start to arrive\, we accept\nan arriving element as long as it is feas
 ible with respect to the new\n``stricter'' matroid and its value passes th
 e precomputed threshold.\nIn addition\, we guarantee that our algorithm ac
 hieves the 1/2\nguarantee not simply with respect to the prophet's expecte
 d gain\, but\nwith respect to the stronger ex-ante relaxation value. \nThu
 s\, we provide the first almost non-adaptive algorithm for the\nmatroid pr
 ophet inequality that achieves the best-possible\napproximation guarantee 
 of 1/2. If time permits\, we will also discuss\nhow we used LLM in this pr
 oject.
DTSTAMP:20260723T074533Z
END:VEVENT
END:VCALENDAR