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=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.