The Maximum Flow Network Interdiction Problem: Valid inequalities, integrality gaps, and approximability

被引：75

作者：

Altner, Douglas S. ^{[1
]}

Ergun, Oezlem ^{[2
]}

Uhan, Nelson A. ^{[3
]}

机构：

[1] USN Acad, Dept Math, Annapolis, MD 21402 USA

[2] Georgia Inst Technol, H Milton Stewart Sch Ind & Syst Engn, Atlanta, GA 30332 USA

[3] Purdue Univ, Sch Ind Engn, W Lafayette, IN 47907 USA

来源：

OPERATIONS RESEARCH LETTERS | 2010年 / 38卷 / 01期

关键词：

Network flows; Integer programming; Integrality gap; Valid inequalities; CRITICAL INFRASTRUCTURE;

D O I：

10.1016/j.orl.2009.09.013

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：33 / 38

页数：6

共 19 条

[1]

Ahuja R., 1993, NETWORK FLOWS THEORY

[2] A NETWORK INTERDICTION MODEL FOR HOSPITAL INFECTION CONTROL [J].