کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427465 686509 2010 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online knapsack with resource augmentation
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Online knapsack with resource augmentation
چکیده انگلیسی

It is known that online knapsack is not competitive. This negative result remains true even if items are removable. In this paper we consider online removable knapsack with resource augmentation, in which we hold a knapsack of capacity R⩾1R⩾1 and aim at maintaining a feasible packing to maximize the total profit of items packed into the knapsack. Both scenarios that removal of accepted items is allowed and is not allowed are investigated. We evaluate an online algorithm by comparing the resulting packing to an optimal packing that uses a knapsack of capacity one. Optimal online algorithms are derived for both the weighted case (items have arbitrary profits) and the unweighted case (the profit of an item is equal to its size).

Research highlights
► Online knapsack with removal is not competitive.
► With augmentation it is competitive and the greedy algorithm is best possible.
► For the online subset sum problem resource augmentation is helpful if removal is not allowed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 110, Issue 22, 31 October 2010, Pages 1016–1020
نویسندگان
, ,