کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
483019 | 1446194 | 2007 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the bin packing problem with a fixed number of object weights
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the bin packing problem with a fixed number of object weights On the bin packing problem with a fixed number of object weights](/preview/png/483019.png)
چکیده انگلیسی
We consider a bin packing problem where the number of different object weights is fixed to C. We analyze a simple approximate approach and show that it leads to an asymptotically exact polynomial algorithm with absolute error 0 if C = 2, at most 1 if 1 < C ⩽ 6, and at most 1 + ⌊(C − 1)/3⌋ if C > 6. A consequence of our analysis is a new upper bound on the gap between the optimal value of the problem at hand and the round-up of the optimal value of the linear relaxation of its Gilmore–Gomory formulation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 181, Issue 1, 16 August 2007, Pages 117–126
Journal: European Journal of Operational Research - Volume 181, Issue 1, 16 August 2007, Pages 117–126
نویسندگان
Carlo Filippi,