Scheduling Split Intervals

Abstract

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 \geq 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 \geq 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.