کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141789 | 957091 | 2008 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
More on online bin packing with two item sizes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We follow the work of [G. Gutin, T. Jensen, A. Yeo, On-line bin packing with two item sizes, Algorithmic Operations Research 1 (2) (2006)] and study the online bin packing problem, where every item has one of two possible sizes which are known in advance. We focus on the parametric case, where both item sizes are bounded from above by 1k for some natural number k≥1k≥1. We show that for every possible pair of item sizes, there is an algorithm with competitive ratio of at most (k+1)2k2+k+1. We prove that this bound is tight for every kk and, moreover, that it cannot be achieved if the two item sizes are not known in advance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 5, Issue 4, November 2008, Pages 705–713
Journal: Discrete Optimization - Volume 5, Issue 4, November 2008, Pages 705–713
نویسندگان
Leah Epstein, Asaf Levin,