Simple algorithms for a weighted interval selection problem

T. Erlebach, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

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 ½ -approximation in the case of unit weights, a ⅛ -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.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
EditorsG. Goos, J. Hartmanis, J. van Leeuwen, D.T. Lee, S.H. Teng
Place of PublicationBerlin
PublisherSpringer
Pages228-240
Number of pages13
ISBN (Electronic)978-3-540-40996-0
ISBN (Print)978-3-540-41255-7
DOIs
Publication statusPublished - 2000
Externally publishedYes
Event11th Annual International Symposium on Algorithms and Computation, (ISAAC 2000) - Taipei, Taiwan
Duration: 18 Dec 200020 Dec 2000
Conference number: 11

Publication series

NameLecture Notes in Computer Science
Volume1969
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th Annual International Symposium on Algorithms and Computation, (ISAAC 2000)
Abbreviated titleISAAC 2000
CountryTaiwan
CityTaipei
Period18/12/0020/12/00

Fingerprint Dive into the research topics of 'Simple algorithms for a weighted interval selection problem'. Together they form a unique fingerprint.

Cite this