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:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69cf6c330a562
DTSTART;TZID=America/Toronto:20240920T133000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240920T150000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/co-reading-g
 roup-david-aleman-1
SUMMARY:C&O Reading Group - David Aleman
CLASS:PUBLIC
DESCRIPTION:TITLE: LP based approximation algorithm for an stochastic match
 ing\nproblem\n\nSPEAKER:\n David Aleman\n\nAFFILIATION:\n University of Wa
 terloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: Consider the random graph model
  where each edge e has a\nfixed weight w_e and it is independently presen
 t in the graph with\nprobability p_e​. Given these probabilities\, we w
 ant to construct a\nmaximum weight matching in the graph. One can only det
 ermine if an\nedge is present by querying it\, and if an edge is present\,
  it must be\nirrevocably included in the matching. Additionally\, each ver
 tex i can\nbe queried no more than t_i times. The goal is to device an ad
 aptive\npolicy (algorithm) to query the edges of the graph one by one in o
 rder\nto maximize the expected weight of the matching.\n\nIn this talk we 
 present an elegant LP-based constant-factor\napproximation algorithm with 
 respect to the optimal adaptive policy\nfor the problem.\n\nThis is one of
  the results due to Bansal\, Gupta\, Li\, Mestre\,\nNagarajan\, and Rudra\
 , in their paper \"When LP is the Cure for your\nMatching Woes\" from 2011
 .
DTSTAMP:20260403T072851Z
END:VEVENT
END:VCALENDAR