开发者

How can we prove that Job Scheduling Problem with penalties is in NP?

How can we prove that Job Scheduling Problem with penalties is in NP开发者_运维技巧?


According to these course notes, reduction from Subset Sum can be used to show that Job Scheduling with penalties is also NP-complete.


The standard nondeterministic approach ("guess then check") should work here: Guess how the jobs should be scheduled, then check that this schedule comes in under the penalty limit (which is obviously possible in polynomial time).

Usually, showing that a problem is in NP is relatively easy -- the harder part is showing that it is also NP-complete (but in this case, you don't seem to need to do that).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜