Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 36:
=== Weighted ===
When the intervals have weights, the problem is equivalent to finding a maximum-weight [[Independent set (graph theory)|independent set]] in an [[interval graph]]. It can be solved in polynomial time.<ref name=":0">{{Cite journal|last=Bar-Noy|first=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|date=2001-09-01|title=A unified approach to approximating resource allocation and scheduling|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|issn=0004-5411}}</ref>
==Group Interval Scheduling Decision==
Line 98:
* Group #2: {[1..3]}
The greedy algorithm selects only 1 interval [0..2] from group #1, while an optimal scheduling is to select [1..3] from group #2 and then [4..6] from group #1.
A more general approximation algorithm attains a 2-factor approximation for the weighted case.<ref name=":0" />
=== LP based approximation algorithms ===
Using the technique of [[Linear programming relaxation]], it is possible to approximate the optimal scheduling with slightly better approximation factors. The approximation ratio of the first such algorithm is asymptotically 2 when ''k'' is large, but when ''k=2'' the algorithm achieves an approximation ratio of 5/3.<ref name=Spieksma/> The approximation factor for arbitrary ''k'' was later improved to 1.582.<ref name="ChuzoiEtAl">{{Cite journal | doi = 10.1287/moor.1060.0218| title = Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems| journal = Mathematics of Operations Research| volume = 31| issue = 4| pages = 730| year = 2006| last1 = Chuzhoy | first1 = J. | author1-link = Julia Chuzhoy | last2 = Ostrovsky | first2 = R. | author2-link = Rafail Ostrovsky| last3 = Rabani | first3 = Y. | citeseerx = 10.1.1.105.2578}}</ref>
==Graph representations==
| |||