کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426011 | 685981 | 2013 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Online selection of intervals and t-intervals
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A t-interval is a union of at most t half-open intervals on the real line. An interval is the special case where t=1t=1. In this paper we study the problems of online selection of intervals and t-intervals. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for selecting intervals, 2-intervals and t -intervals, for any t>2t>2. While offline t-interval selection has been studied before, the online version is considered here for the first time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 233, December 2013, Pages 1–11
Journal: Information and Computation - Volume 233, December 2013, Pages 1–11
نویسندگان
Unnar Th. Bachmann, Magnús M. Halldórsson, Hadas Shachnai,