Hardness and Approximation for Network Flow Interdiction
Chestnut, Stephen R.; Zenklusen, Rico;
Subject: Mathematics - Optimization and Control | Computer Science - Data Structures and Algorithms
In the Network Flow Interdiction problem an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem despite decades of interest in it. We present the first approximation hardness, showing th... View more
 N. Assimakopoulos. A network interdiction model for hospital infection control. Computers in Biology and Medicine, 17(6):413-422, 1987.
 C. Bazgan, S. Toubaline, and D. Vanderpooten. Complexity of determining the most vital elements for the p-median and p-center location problems. Journal of Combinatorial Optimization, 25(2):191-207, 2013.
 C. Bazgan, S. Toubaline, and D. Vanderpooten. Critical edges for the assignment problem: Complexity and exact resolution. Operations Research Letters, 41(6):685- 689, 2013.
 C. Bazgan, S. Toubaline, and D. Vanderpooten. Critical edges/nodes for the minimum spanning tree problem: complexity and approximation. Journal of Combinatorial Optimization, 26(1):178-189, 2013.
 A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. In Proceedings of the forty-second ACM Symposium on Theory of Computing, pages 201- 210, 2010.
 A. Bhaskara, M. Charikar, A. Vijayaraghavan, V. Guruswami, and Y. Zhou. Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph. In Proceedings of the twenty-third annual ACM-SIAM Symposium on Discrete Algorithms, pages 388- 405, 2012.
 C. Burch, R. Carr, S. Krumke, M. Marathe, C. Phillips, and E. Sundberg. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In Network Interdiction and Stochastic Integer Programming, pages 51-68. Springer, 2003.
 Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, and Yuan Zhou. Approximation algorithms and hardness of the k-route cut problem. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 780-799, 2012.
 M. Dinitz and A. Gupta. Packing interdiction and partial covering problems. In Integer Programming and Combinatorial Optimization, pages 157-168. Springer, 2013.
 U. Feige. Relations between average case complexity and approximation complexity. In Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing, pages 534-543, 2002.