Online selection of intervals and t-intervals ?
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=1 t = 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>2 t > 2 . While offline t-interval selection has been studied before, the online version is considered here for the first time.
interval selection online algorithms competitive analysis