Online selection of intervals and t-intervals

Unnar Th Bachmann, Magnús M. Halldórsson, Hadas Shachnai*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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. 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. While offline t-interval selection has been studied before, the online version is considered here for the first time.

Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalInformation and Computation
Publication statusPublished - 2013

Other keywords

  • Competitive analysis
  • Interval selection
  • Online algorithms


Dive into the research topics of 'Online selection of intervals and t-intervals'. Together they form a unique fingerprint.

Cite this