کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435313 689892 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On Lazy Bin Covering and Packing problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On Lazy Bin Covering and Packing problems
چکیده انگلیسی

In this paper, we study two interesting variants of the classical bin packing problem, called Lazy Bin Covering (LBC) and Cardinality Constrained Maximum Resource Bin Packing (CCMRBP) problems. For the offline LBC problem, we first prove the approximation ratio of the First-Fit-Decreasing and First-Fit-Increasing algorithms, then present an APTAS. For the online LBC problem, we give a competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONICM algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem Boyar et al. (2006) [1]. For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 411, Issue 1, 1 January 2010, Pages 277-284