Interval scheduling: Difference between revisions

Revision as of 09:47, 3 September 2021

Revision as of 09:51, 3 September 2021

Line 89:

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>

==Related problems==

==Graph representations==

An interval scheduling problem can be described by an [[intersection graph]], where each vertex is an interval, and there is an edge between two vertices if and only if their intervals overlap. In this representation, the interval scheduling problem is equivalent to finding the maximum [[Independent set (graph theory)|independent set]] in this intersection graph. In general graphs, findingFinding a maximum independent set is NP-hard. Therefore, it is interesting that in interval intersectiongeneral graphs, but it can be done exactly in polynomial time. {{citationin the special case needed|date=Aprilof 2016}}intersection graphs (ISMP).

A group-interval scheduling problem, i.e. (GISMPk,) can be described by a similar interval-intersection graph, with additional edges between each two intervals of the same group, i.e., this is the edge union of an interval graph and a graph consisting of n disjoint cliques of size ''k''.

==Variations==