Scheduling split intervals

We consider the problem of scheduling jobs that are given as groups of nonintersecting segments on the real line. Each job J(j) is associated with an interval, I-j, which consists of up to t segments, for some t >= 1, and a weight (profit), w(j); 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.