History


Please fill in your query. A complete syntax description you will find on the General Help page.
Online selection of intervals and $t$-intervals. (English)
Kaplan, Haim (ed.), Algorithm theory ‒ SWAT 2010. 12th Scandinavian symposium and workshops on algorithm theory, Bergen, Norway, June 21‒23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13730-3/pbk). Lecture Notes in Computer Science 6139, 383-394 (2010).
Summary: 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$. Requests for contiguous allocation of a linear resource can be modeled as a sequence of $t$-intervals. We consider the problems of online selection of intervals and $t$-intervals, which show up in Video-on-Demand services, high speed networks and molecular biology, among others. 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$. While offline $t$-interval selection has been studied before, the online version is considered here for the first time.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!