## 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 ≥ 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.

Original language | English |
---|---|

Pages (from-to) | 1-15 |

Number of pages | 15 |

Journal | SIAM Journal on Computing |

Volume | 36 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2006 |

## Other keywords

- Approximation algorithm
- Independent set
- Interval graph
- Scheduling