Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426011 | Information and Computation | 2013 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Unnar Th. Bachmann, Magnús M. Halldórsson, Hadas Shachnai,