Interval selection: Applications, algorithms, and lower bounds

Abstract

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 GREEDYalpha 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 alpha so that GREEDYalpha produces a 2-approximation in the case of unit weights, an 8-approximation in the case of arbitrary weights, and a (3+2*sqrt(2))-approximation in the case where the weights of all intervals corresponding to the same job are equal. If all intervals have the same length, we prove for m=1,2 that GREEDYalpha achieves ratio 6.638 in the case of arbitrary weights and 5 in the case of equal weights per job. Concerning lower bounds, we show that for instances with intervals of arbitrary lengths, no deterministic myopic algorithm can achieve ratio better than 2 in the case of unit weights, better than approximately 7.103 in the case of arbitrary weights, and better than 3+2*sqrt(2) in the case where the weights of all intervals corresponding to the same job are equal. If all intervals have the same length, we give lower bounds of 3+2*sqrt(2) for the case of arbitrary weights and 5 for the case of equal weights per job. Furthermore, we give a lower bound of e/(e-1)=1.582 on the approximation ratio of randomized myopic algorithms in the case of unit weights.