کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438252 | 690245 | 2008 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Online bin packing with arbitrary release times
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study a new variant of the online bin-packing problem, in which each item ai is associated with a size ai and also a release time ri so that it must be placed at least ri above the bottom of a bin. Items arrive in turn and must be assigned without any knowledge of subsequent items. The goal is to pack all items into unit-size bins using the minimum number of bins. We study the problem with all items have equal size. First, we show that the ANY FIT algorithm cannot be approximated within any constant. Then we present a best possible online algorithm with asymptotic competitive ratio of two.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 390, Issue 1, 22 January 2008, Pages 110-119
Journal: Theoretical Computer Science - Volume 390, Issue 1, 22 January 2008, Pages 110-119