Space-constrained interval selection

Yuval Emek, Magnús M. Halldórsson, Adi Rosén

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic 2-approximation streaming algorithm for this problem is developed, together with an algorithm for the special case of proper intervals, achieving improved approximation ratio of 3/2.We complement these upper bounds by proving that they are essentially the best possible in the streaming setting: It is shown that an approximation ratio of 2 - ϵ (or 3/2 - ϵ for proper intervals) cannot be achieved unless the space is linear in the input size. In passing, we also answer an open question of Adler and Azar (J. Scheduling 2003) regarding the space complexity of constant-competitive randomized preemptive online algorithms for the same problem.

Original languageEnglish
Article number51
JournalACM Transactions on Algorithms
Volume12
Issue number4
DOIs
Publication statusPublished - Sept 2016

Bibliographical note

Publisher Copyright:
© 2016 ACM.

Other keywords

  • Interval selection
  • Lower bounds
  • Online algorithms
  • Streaming algorithms

Fingerprint

Dive into the research topics of 'Space-constrained interval selection'. Together they form a unique fingerprint.

Cite this