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:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20221106T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:682e21112ee43
DTSTART;TZID=America/Toronto:20221202T120000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20221202T120000
URL:/combinatorics-and-optimization/events/combinatoria
 l-optimization-reading-group-jacob-skitsko
SUMMARY:Combinatorial Optimization Reading Group - Jacob Skitsko
CLASS:PUBLIC
DESCRIPTION:Summary \n\nTITLE: Boosted Sampling\n\nSpeaker:\n Jacob Skitsko
 \n\nAffiliation:\n University of À¶Ý®ÊÓƵ\n\nLocation:\n MC 6029 or contac
 t Rian Neogi for Zoom link\n\nABSTRACT: We will discuss the boosted samp
 ling technique introduced by\nGupta et al. which approximates the stochast
 ic version of problems by\nusing nice approximation algorithms for the det
 erministic version of\nthe problem. We will focus on rooted stochastic Ste
 iner trees as an\nexample\, though other problems are covered by this appr
 oach (such as\nvertex cover and facility location). The problem is given t
 o us in two\nstages: in the first stage we may choose some elements at a c
 heaper\ncost\, and in the second stage our actual requirements are reveale
 d to\nus\, and we can buy remaining needed elements at a more expensive co
 st\n(where costs get scaled by some factor in the second stage). We will\n
 see that if our problem is sub-additive\, and we have an\nalpha-approximat
 ion algorithm for the deterministic version of our\nproblem with a beta-st
 rict cost-sharing function then we can get an\n(alpha + beta)-approximatio
 n for the stochastic version of our\nproblem. We also discuss related prob
 lems\, for example the (not\nsub-additive!) unrooted stochastic Steiner tr
 ee problem.\n 
DTSTAMP:20250521T185305Z
END:VEVENT
END:VCALENDAR