Symmetric Interdiction for Matching Problems
||Thursday, October 13, 2016
||12:00pm - 1:00pm
||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.