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:6a2b78aa6a979
DTSTART;TZID=America/Toronto:20260612T113000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260612T123000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read
 inggroup-sina-kalantarzadeh-designing-ptas
SUMMARY:CombOpt ReadingGroup - Sina Kalantarzadeh-Designing a PTAS for\nPhi
 losopher Inequalities under Constant-Depth Laminar Constraints
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n\n Sina Kalantarzadeh\n\nAFFILIATION:\n University of
  Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT:\n\nIn stochastic online opti
 mization\, prophet inequalities under matroid\nconstraints have been studi
 ed extensively. The philosopher\nbenchmark(optimal online strategy) is wea
 ker than the prophet\nbenchmark\, but it is still not fully understood how
  well one can\ncompete against the optimal online strategy using polynomia
 l\ncomputational power. Pashkovich and Dehaan showed that it is\nimpossibl
 e to design a PTAS for computing optimal online strategy in\ngraphic matro
 ids. \nIn this talk we consider a special class of matroid constraints so\
 ncalled laminar matroids. There are (n) items arriving in a known\norder\,
  and each item has a probability distribution over its realized\nvalue. We
  are also given a collection of bins on these items\, where\neach bin (B) 
 has a capacity (c(B)). The bins form a laminar family.\nWhen an item arriv
 es\, its value is revealed\, and the algorithm must\nimmediately decide wh
 ether to accept or reject it\, while respecting\nall laminar capacity cons
 traints. The goal is to maximize the expected\ngain of the total value of 
 the accepted items and compare it to the\ngain of the optimal online polic
 y\, rather than to the prophet.\nAnari et al. designed a polynomial-time a
 pproximation scheme(PTAS) for\nconstant-depth instances\, meaning that eac
 h item belongs to only a\nconstant number of bins. Their approach uses the
  fact that the optimal\nonline policy can be formulated as a linear progra
 m(LP). We will first\nexamine this LP in the simple case where the laminar
  family consists\nof a single bin of capacity one. In general\, however\, 
 the LP has\nexponential size and therefore cannot be solved directly in po
 lynomial\ntime. The main idea is to select certain small bins inside the l
 aminar\nfamily for which the corresponding subproblems are no longer\nexpo
 nentially large. On these selected parts\, one can use the optimal\nonline
  policy\, and then combine these local policies to obtain a\nglobal approx
 imation. It remains open whether one can design a PTAS\nfor general lamina
 r families. 
DTSTAMP:20260612T031034Z
END:VEVENT
END:VCALENDAR