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.
scheduling independent set interval graph approximation algorithm