کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10523843 | 957101 | 2005 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simple lifted cover inequalities and hard knapsack problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider a class of random knapsack instances described by Chvátal, who showed that with probability going to 1, such instances require an exponential number of branch-and-bound nodes. We show that even with the use of simple lifted cover inequalities, an exponential number of nodes is required with probability going to 1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 2, Issue 3, September 2005, Pages 219-228
Journal: Discrete Optimization - Volume 2, Issue 3, September 2005, Pages 219-228
نویسندگان
Brady Hunsaker, Craig A. Tovey,