کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331291 | 686668 | 2005 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Modified subset sum heuristics for bin packing
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We analyze the worst-case ratio of natural variations of the so-called subset sum heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. Namely, we consider the variation in which the largest remaining item is packed in the current bin, and then the remaining capacity is filled as much as possible, as well as the variation in which all items larger than half the capacity are first packed in separate bins, and then the remaining capacity is filled as much as possible. For both variants, we show a nontrivial upper bound of 13/9 on the worst-case ratio, also discussing lower bounds on this ratio.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 96, Issue 1, 16 October 2005, Pages 18-23
Journal: Information Processing Letters - Volume 96, Issue 1, 16 October 2005, Pages 18-23
نویسندگان
Alberto Caprara, Ulrich Pferschy,