کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427918 686576 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online algorithms for the general k-search problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Online algorithms for the general k-search problem
چکیده انگلیسی

This paper investigates the general k-search problem, in which a player is to sell totally k units of some asset within n   periods, aiming at maximizing the total revenue. At each period, the player observes a quoted price which expires before the next period, and decides irrecoverably the amount of the asset to be sold at the price. We present a deterministic online algorithm and prove it optimal for the case where k⩽n−1k⩽n−1. For the other case where k⩾nk⩾n, we show by numerical illustration that the gap between the upper and the lower bound of competitive ratio is quite small for many situations.


► We investigate the general k-search problem.
► We present a deterministic DET online algorithm and prove the competitive ratio.
► We present a lower bound for this problem.
► Algorithm DET performs very well for the general k-search problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 14, 31 July 2011, Pages 678–682
نویسندگان
, , , ,