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:69e56f5674816
DTSTART;TZID=America/Toronto:20260323T123000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260323T133000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/co-reading-g
 roup-noah-weninger-simple-2epsilon-approximation
SUMMARY:C&O Reading Group - Noah Weninger-A Simple\n$(2+\\epsilon)$-Approxi
 mation for Knapsack Interdiction
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n\n Noah Weninger\n\nAFFILIATION:\n University of Wate
 rloo\n\nLOCATION:\n MC 6029\n\nABSTRACT:In the knapsack interdiction probl
 em\, there are two players\nand $n$ items\, each with some profit\, remova
 l cost\, and packing\nweight. First\, the interdictor selects items to rem
 ove\; the total\nremoval cost must fit within the interdiction budget. The
 n\, the\nfollower solves a knapsack problem on the remaining items. The\no
 bjective is to select an interdiction set which minimizes the\nfollower's 
 maximum profit. This problem is $\\Sigma_2^p$-complete.\n\nWe present a $(
 2+\\epsilon)$-approximation with running time polynomial\nin $n$ and $1/\\
 epsilon$. We start by showing that after LP-relaxing\nthe follower's knaps
 ack\, the problem becomes solvable with dynamic\nprogramming in pseudopoly
 nomial time\, and yields a 2-approximation for\nthe original problem. We t
 hen show that this dynamic program can be\nrounded to get an FPTAS for the
  2-approximate problem. Although there\nis already a PTAS known for knapsa
 ck interdiction (Chen et al\, 2022)\,\nour algorithm is considerably simpl
 er and faster: to achieve a\n3-approximation\, the PTAS needs running time
  $\\Omega(n^{100})$\,\nwhereas ours is only $\\tilde O(n^3)$.
DTSTAMP:20260420T001206Z
END:VEVENT
END:VCALENDAR