Interval selection: Applications, algorithms, and lower bounds

Given a set of jobs, each consisting of a number of weighted intervals on the real line, and a positive integer m, we study the problem of selecting a maximum weight subset of the intervals such that at most one interval is selected from each job and, for any point p on the real line, at most m intervals containing p are selected. This problem has applications in molecular biology, caching, PCB assembly, combinatorial auctions, and scheduling. It generalizes the problem of finding a (weighted) maximum independent set in an interval graph. We give a parameterized algorithm GREEDY", that belongs to the class of "myopic" algorithms, which are deterministic algorithms that process the given intervals in order of non-decreasing right endpoint and can either reject or select each interval (rejections are irrevocable). We show that there are values of the parameter a so that GREEDY", produces a 2-approximation in the case of unit weights, an 8-approximation in the case of arbitrary weights, and a (3 + 2V2)-approximation in the case where the weights of all intervals corresponding to the same job are equal. If all intervals have the same length