کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1143356 957195 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Maximum Flow Network Interdiction Problem: Valid inequalities, integrality gaps, and approximability
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Maximum Flow Network Interdiction Problem: Valid inequalities, integrality gaps, and approximability
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 38, Issue 1, January 2010, Pages 33–38
نویسندگان
, , ,