|
Authors: | Thomas Erlebach, Frits Spieksma |
Group: | Theory of Communication Networks |
Type: | Inproceedings |
Title: | Simple algorithms for a weighted interval selection problem |
Year: | 2000 |
Month: | December |
Pub-Key: | ES00i |
Book Titel: | Lecture Notes in Computer Science. Proceedings of the Eleventh Annual International Symposium on Algorithms And Computation ISAAC00 |
Volume: | 1969 |
Pages: | 228-240 |
Keywords: | interval scheduling |
Abstract: | 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(alpha) and show that there are values of the parameter alpha so that GREEDY(alpha) produces a 1/2-approximation in the case of unit weights, a 1/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. Algorithm GREEDY(alpha) belongs to the class of "myopic" algorithms, which are 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(alpha) 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. |
Location: | Taipei, Taiwan |
Resources: | [BibTeX] |