Title: Simple algorithms for a weighted interval selection problem
Authors: Erlebach, T. ×
Spieksma, Frederik #
Issue Date: Dec-2000
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:1969 pages:228-240
Conference: Proceedings of the Annual International Symposium on Algorithms and Computation (ISAAC '00) edition:11 location:Taipei (Taiwan) date:18-20 December 2000
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α and show that there are values of the parameterα so that GREEDYα produces a 1/2-approximation in the case of unit weights, a 1/8-approximation in the case of arbitrary weights, and a (3 - 2p2)-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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Non-KU Leuven Association publications
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
simplealgorithmsspieksma.pdf Published 130KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science