Hardness and Approximation for Network Flow Interdiction

Preprint English OPEN
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
Share - Bookmark