2015/11/08 by Stephen R. Chestnut, Rico Zenklusen, Chestnut, Stephen R. +1 · 1 citation
Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Infrastructure Resilience and Vulnerability Analysis #Optimization and Control (math.OC) #Reliability and Maintenance Optimization
paper · pdf · doi:10.48550/arxiv.1511.02484
openalex publication_date 2015/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Interdiction problems ask about the worst-case impact of a limited change to\nan underlying optimization problem. They are a natural way to measure the\nrobustness of a system, or to identify its weakest spots. Interdiction problems\nhave been studied for a wide variety of classical combinatorial optimization\nproblems, including maximum s-t flows, shortest s-t paths, maximum\nweight matchings, minimum spanning trees, maximum stable sets, and graph\nconnectivity. Most interdiction problems are NP-hard, and furthermore, even\ndesigning efficient approximation algorithms that allow for estimating the\norder of magnitude of a worst-case impact, has turned out to be very difficult.\nNot very surprisingly, the few known approximation algorithms are heavily\ntailored for specific problems.\n Inspired by an approach of Burch et al. (2003), we suggest a general method\nto obtain pseudoapproximations for many interdiction problems. More precisely,\nfor any \α>0, our algorithm will return either a\n(1+\α)-approximation, or a solution that may overrun the interdiction\nbudget by a factor of at most 1+\α-1 but is also at least as good as\nthe optimal solution that respects the budget. Furthermore, our approach can\nhandle submodular interdiction costs when the underlying problem is to find a\nmaximum weight independent set in a matroid, as for example the maximum weight\nforest problem. The approach can sometimes be refined by exploiting additional\nstructural properties of the underlying optimization problem to obtain stronger\nresults. We demonstrate this by presenting a PTAS for interdicting b-stable\nsets in bipartite graphs.\n