Interval scheduling: Difference between revisions

Revision as of 22:28, 8 November 2023

Revision as of 17:34, 26 November 2023

Line 164:

=== 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 = 730730–738
| year = 2006
| last1 = Chuzhoy | first1 = J.Julia | author1-link = Julia Chuzhoy
| last2 = Ostrovsky | first2 = R.Rafail | author2-link = Rafail Ostrovsky| last3 = Rabani | first3 = Y. | citeseerx = 10.1.1.105.2578}}</ref>

| last3=Rabani | first3=Yuval

| citeseerx=10.1.1.105.2578}}</ref>

==Related problems==