Algorithms Seminar

Symmetric Interdiction for Matching Problems

Speaker:Sam Haney
Date: Thursday, October 13, 2016
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


In this work, we consider the following question: how can a network administrator throttle traffic on a network when he cannot distinguish between legitimate and malicious traffic, in a way that is least disruptive to legitimate users? To model this, we introduce symmetric matching interdiction, which can be simply stated as: find a matching whose removal minimizes the size of the maximum matching in the remaining graph. We show that this problem is APX-hard, and obtain a 3/2-approximation algorithm.


Samuel Haney is 4th year Phd student at Duke advised by Debmalya Panigrahi. He works on graph algorithms.