Interdicting Structured Combinatorial Optimization Problems with {0,1}-Objectives

Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system or to identify its weakest spots. Interdiction problems have been studied for a wide variety of classical combinatorial optimization problems. Most interdiction problems are NP-hard, and furthermore, even designing efficient approximation algorithms that allow for estimating the order of magnitude of a worst-case impact has turned out to be very difficult. Not very surprisingly, the few known approximation algorithms are heavily tailored for specific problems. Inspired by previous approaches to network flow interdiction we suggest a general method to obtain pseudoapproximations for many interdiction problems. More precisely, for any alpha > 0, our algorithm will return either a (1 + alpha)-approximation or a solution that may overrun the interdiction budget by a factor of at most 1 + 1/alpha but is also at least as good as the optimal solution that respects the budget. Furthermore, our approach can handle submodular interdiction costs when the underlying problem is to find a maximum weight independent set in a matroid. Additionally, our approach can sometimes be refined by exploiting additional structural properties of the underlying optimization problem to obtain stronger results. We demonstrate this by presenting a polynomial-time approximation scheme for interdicting b-stable sets in bipartite graphs.