کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420295 683920 2010 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the sum minimization version of the online bin covering problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the sum minimization version of the online bin covering problem
چکیده انگلیسی

Given a set of mm identical bins of size 1, the online input consists of a (potentially infinite) stream of items in (0,1](0,1]. Each item is to be assigned to a bin upon arrival. The goal is to cover all bins, that is, to reach a situation where a total size of items of at least 1 is assigned to each bin. The cost of an algorithm is the sum of all used items at the moment when the goal is first fulfilled. We consider three variants of the problem, the online problem, where there is no restriction of the input items, and the two semi-online models, where the items arrive sorted by size, that is, either by non-decreasing size or by non-increasing size. The offline problem is considered as well.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 13, 6 July 2010, Pages 1381–1393
نویسندگان
, , , ,