کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421304 684186 2010 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
clever or smart: Strategies for the online target date assignment problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
clever or smart: Strategies for the online target date assignment problem
چکیده انگلیسی

In this paper, we consider the Online Target Date Assignment Problem (OnlineTDAP) for general downstream problems, where the downstream cost are nonnegative, additive and satisfy the triangle inequality.We analyze algorithm smart, which was introduced by Angelelli et al. [3] and give its exact competitive ratio depending on the number of requests. Since the obtained competitive ratio is at most 22−1≈1.8284 we answer the question posed in Angelelli et al. [4] if smart has a competitive ratio strictly less than 22.Moreover, we introduce a new algorithm called clever and show that this strategy has a competitive ratio of 3/23/2. We show that this is asymptotically optimal by proving that no online algorithm can perform better than 3/2−ε3/2−ε.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 1, 6 January 2010, Pages 71–79
نویسندگان
, , , ,