【正文】
efinition of NPCompleteness pYX??If X is P, then Y is P ?IF Y is NP, then X is NP Definition of NPCompleteness ? Independent Set amp。 Vertex Cover IS: If there is IS of G in size of =k VC: If there is IS of G in size of =k Definition of NPCompleteness Example1: ? Observation: S V is IS if and only if V\S is VC of the graph G ? Conclusion: IS VC amp。 | | , . . iiSS m S k s t S U?? ? ? ?Definition of NPCompleteness 我們怎樣證明一個問題是 NPC的呢? ? 定義: 如果問題 X滿足以下條件,那么 X屬于 NPC。 2. 定義機器 i的負(fù)載為: 3. 定義總負(fù)載: 4. 目標(biāo):最小化總負(fù)載 iijjMTt?? ?m a x iiTT?Approximation Algorithm 近似算法 1 每次任意選擇一個未安排的工作,將它安排在當(dāng)前負(fù)載最小的機器上 ?這是一個 2倍近似算法 Approximation Algorithm 證明: 1. 2. 假設(shè) Mi 是負(fù)載最大的機器,工作 j是機器 i最后一個工作,我們有: 1 amp。 m a xjj jjO P T t O P T tm???12*i j kk