Content deleted Content added
Bluelink 1 book for verifiability.) #IABot (v2.0) (GreenC bot |
m Task 18 (cosmetic): eval 6 templates: del empty params (2×); del |ref=harv (1×); |
||
Line 51:
| date = July 1998
| isbn = 978-0-486-40258-1
}}</ref> to be [[NP-complete]] likewise to the unrestricted version.
Line 77 ⟶ 76:
=== MaxSNP-complete when some groups contain 2 or more intervals ===
GISMPk is NP-complete even when <math>k\geq 2</math>.<ref name=Spieksma>{{Cite journal | last1 = Spieksma | first1 = F. C. R. | title = On the approximability of an interval scheduling problem | doi = 10.1002/(sici)1099-1425(199909/10)2:5<215::aid-jos27>3.0.co;2-y | journal = Journal of Scheduling | volume = 2 | issue = 5 | pages = 215–227 | year = 1999
Moreover, GISMPk is [[MaxSNP]]-complete, i.e., it does not have a PTAS unless P=NP. This can be proved by showing an approximation-preserving reduction from MAX 3-SAT-3 to GISMP2.<ref name=Spieksma/>
| |||