|
|||||
|
|
The Maximum Flow Network Interdiction Problem: Valid inequalities, integrality gaps, and approximability |
|
| Authors: | Douglas S. Altner,Ö zlem Ergun |
| Affiliation: | a Department of Mathematics, United States Naval Academy, Annapolis, MD, United States b H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, United States c School of Industrial Engineering, Purdue University, West Lafayette, IN, United States |
| Abstract: | 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. |
| Keywords: | Network flows Integer programming Integrality gap Valid inequalities |
| 本文献已被 ScienceDirect 等数据库收录！ | |