Show simple item record

dc.contributor.author
Erlebach, Thomas
dc.contributor.author
Spieksma, Frits C.R.
dc.date.accessioned
2022-08-11T07:01:03Z
dc.date.available
2017-06-13T03:59:37Z
dc.date.available
2022-08-11T07:01:03Z
dc.date.issued
2002-10
dc.identifier.uri
http://hdl.handle.net/20.500.11850/146997
dc.identifier.doi
10.3929/ethz-a-004446236
dc.description.abstract
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 GREEDYalpha 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 alpha so that GREEDYalpha produces a 2-approximation in the case of unit weights, an 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. If all intervals have the same length, we prove for m=1,2 that GREEDYalpha 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+2*sqrt(2) 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+2*sqrt(2) 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)=1.582 on the approximation ratio of randomized myopic algorithms in the case of unit weights.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich, Computer Engineering and Networks Laboratory
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
Interval selection: Applications, algorithms, and lower bounds
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.journal.title
TIK Report
ethz.journal.volume
152
en_US
ethz.size
45 p.
en_US
ethz.version.edition
Version 2 (Revised: November 28, 2002)
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
en_US
ethz.date.deposited
2017-06-13T04:00:39Z
ethz.source
ECOL
ethz.identifier.importid
imp59366a629b73038758
ethz.ecolpid
eth:25967
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-13T17:07:50Z
ethz.rosetta.lastUpdated
2020-02-15T01:30:00Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Interval%20selection:%20Applications,%20algorithms,%20and%20lower%20bounds&rft.jtitle=TIK%20Report&rft.date=2002-10&rft.volume=152&rft.au=Erlebach,%20Thomas&Spieksma,%20Frits%20C.R.&rft.genre=report&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record