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:6a6ec013d3546
DTSTART;TZID=America/Toronto:20260731T113000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260731T123000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read
 inggroup-sina-kalantarzadeh-minimum-bounded
SUMMARY:CombOpt ReadingGroup - Sina Kalantarzadeh-Minimum Bounded Degree\nS
 panning Trees
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n\n Sina Kalantarzadeh\n\nAFFILIATION:\n University of
  Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: I will present Goemans’s 
 beautiful\, though no longer\nstate-of-the-art\, 2006 result on the Minimu
 m Bounded-Degree Spanning\nTree problem. Given a weighted graph (G=(V\,E))
  and degree bounds\n(B\\to\\mathbb{N})\, the goal is to find a minimum-cos
 t spanning tree (T)\nsatisfying (d_T(v)\\le B(v)) for every (v\\in V). Thi
 s problem is\nNP-hard. Fürer and Raghavachari (1992) gave a polynomial-ti
 me\nalgorithm for the unweighted setting that produces a spanning tree\nsa
 tisfying (d_T(v)\\le B(v)+1). For the weighted problem\, Goemans\ndesigned
  an elegant LP-rounding algorithm that returns a tree of cost\nat most tha
 t of the optimal degree-bounded solution while satisfying\n(d_T(v)\\le B(v
 )+2). I will explain this result and the simple yet\nbeautiful combinatori
 al optimization ideas underlying it. In 2007\,\nSingh and Lau improved the
  violation to (B(v)+1) using iterative\nrelaxation\, which I might give a 
 talk about in later sessions.
DTSTAMP:20260802T035707Z
END:VEVENT
END:VCALENDAR