Simple Algorithms for a Weighted Interval Selection Problem

Given a set of jobs, each consisting of a number of weighted intervals on the real line, and a number m of machines, 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, and scheduling. We give a parameterized algorithm GREEDY# and show that there are values of the parameter # so that GREEDY# produces 2 -approximation in the case of unit weights, a 8 -approximation in the case of arbitrary weights, and a (3 2 # 2)-approximation in the case where the weights of all intervals corresponding to the same job are equal. Algorithm GREEDY# belongs to the class of "myopic" algorithms, which are deterministic algorithms that process the given intervals in order of non-decreasing right endpoints and can either reject or select each interval (rejections are irrevocable). We use competitive analysis to show that GREEDY# is an optimal myopic algorithm in the case of unit weights and in the case of equal weights per job, and is close to optimal in the case of arbitrary weights