کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438233 | 690244 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Online removable knapsack problem under convex function
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we address an online knapsack problem under a convex size–profit function. We first give a greedy online algorithm with a competitive ratio 2. Then we propose an improved online algorithm with a competitive ratio 5/3. We also prove that when the convex function has a specific property, our improved online algorithm is (1+5)/2-competitive, which is optimal. Finally, we prove that the lower bound of this problem is (1+5)/2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volumes 540–541, 26 June 2014, Pages 62–69
Journal: Theoretical Computer Science - Volumes 540–541, 26 June 2014, Pages 62–69
نویسندگان
Xin Han, Yasushi Kawase, Kazuhisa Makino, He Guo,