Scheduling split intervals

R. Bar-Yehuda*, M. M. Halldórsson, J. Naor, H. Shachnai, I. Shapira

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

85 Citations (Scopus)

Abstract

We consider the problem of scheduling jobs that are given as groups of nonintersecting segments on the real line. Each job Jj is associated with an interval, Ij, which consists of up to t segments, for some t ≥ 1, and a weight (profit), wj; two jobs are in conflict if their intervals intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g., bandwidth in linear processor arrays), and computational biology/geometry. The objective is to schedule a subset of nonconflicting jobs of maximum total weight. Our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of t = 1 is an ordinary interval graph). We show that, for t ≥ 2, this problem is APX-hard, even for highly restricted instances. Our main result is a 2t-approximation algorithm for general instances. This is based on a novel fractional version of the Local Ratio technique. One implication of this result is the first constant factor approximation for nonoverlapping alignment of genomic sequences. We also derive a bicriteria polynomial time approximation scheme for a restricted subclass of t-interval graphs.

Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalSIAM Journal on Computing
Volume36
Issue number1
DOIs
Publication statusPublished - 2006

Other keywords

  • Approximation algorithm
  • Independent set
  • Interval graph
  • Scheduling

Fingerprint

Dive into the research topics of 'Scheduling split intervals'. Together they form a unique fingerprint.

Cite this