Interval scheduling: Difference between revisions

Revision as of 15:31, 6 October 2021

Revision as of 17:22, 30 October 2021

Line 19:

==Single-Interval Scheduling Maximization==

=== Unweighted ===

Line 44 ⟶ 43:

GISDPk is NP-complete when <math>k\geq 3</math>,<ref name=NakajimaHakimi>{{Cite journal | doi = 10.1016/0196-6774(82)90030-X| title = Complexity results for scheduling tasks with discrete starting times| year = 1982| last1 = Nakajima | first1 = K. | last2 = Hakimi | first2 = S. L. | journal = Journal of Algorithms| volume = 3| issue = 4| pages = 344}}</ref> even when all intervals have the same length.<ref name=Keil>{{Cite journal | doi = 10.1016/0167-6377(92)90087-j| title = On the complexity of scheduling tasks with discrete starting times| year = 1992| last1 = Mark Keil | first1 = J. | journal = Operations Research Letters| volume = 12| issue = 5| pages = 293–295}}</ref> This can be shown by a reduction from the following version of the [[Boolean satisfiability problem]], which was shown <ref>{{Cite book|last1=Papadimitriou|first1=Christos H.|title=Combinatorial Optimization : Algorithms and Complexity|last2=Steiglitz|first2=Kenneth|date=July 1998|publisher=Dover|isbn=978-0-486-40258-1|author2-link=Kenneth Steiglitz}}</ref> to be [[NP-complete]] likewise to the unrestricted version.

::Let <math>X = \{x_1, x_2,... \dots, x_p\}</math> be a set of Boolean variables. Let <math>C = \{c_1, c_2,... \dots, c_q\}</math> be a set of clauses over ''X'' such that (1) each clause in ''C'' has at most three literals and (2) each variable is restricted to appear once or twice positively and once negatively overall in ''C''. Decide whether there is an assignment to variables of ''X'' such that each clause in ''C'' has at least one true literal.

Given an instance of this satisfiability problem, construct the following instance of GISDP. All intervals have a length of 3, so it is sufficient to represent each interval by its starting time:

* For every variable <math>x_i</math> (for ''i''=1,...,''p''), create a group with two intervals: one starting at <math>50i-10</math> (representing the assignment <math>x_i = \mathrm{false}</math>) and another starting at <math>50i+10</math> (representing the assignment <math>x_i = \mathrm{true}</math>).

* For every clause <math>c_j</math> (for ''j''=1,...,''q''), create a group with the following intervals:

** For every variable <math>x_i</math> that appears positively for the ''first'' time in ''C'' - an interval starting at <math>50i-12</math>.

** For every variable <math>x_i</math> that appears positively for the ''second'' time in ''C'' - an interval starting at <math>50i-8</math>. Note that both these intervals intersect the interval <math>50i-10</math>, associated with <math>x_i = \mathrm{false}</math>.

** For every variable <math>x_i</math> that appears negatively - an interval starting at <math>50i+8</math>. This interval intersects the interval <math>50i+10</math> associated with <math>x_i=true</math>.