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

چکیده انگلیسی
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
Journal: Operations Research Letters - Volume 38, Issue 1, January 2010, Pages 33–38
نویسندگان
Douglas S. Altner, Özlem Ergun, Nelson A. Uhan,