Journal of Algorithms vol:46 issue:1 (Jan.) pages:27-53
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 GA 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 GA 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, we prove for m=1,2 that GA 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+2v2) 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+2v2) 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) (approximately 1.582) on the approximation ratio of randomized myopic algorithms in the case of unit weights.