Journal
OPERATIONS RESEARCH LETTERS
Volume 38, Issue 1, Pages 33-38Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.orl.2009.09.013
Keywords
Network flows; Integer programming; Integrality gap; Valid inequalities
Categories
Funding
- NSF [DMI-0238815]
Ask authors/readers for more resources
We present two classes of polynomially separable valid inequalities for the Maximum Flow Network Interdiction Problem. We prove that the integrality gap of the standard integer program is not bounded by a constant, even when strengthened by our valid inequalities. Finally, we provide an approximation-factor-preserving reduction from a simpler interdiction problem. Published by Elsevier B.V.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available