npc
npc问题与近似算法
iijjMTt m a x iiTTApproximation Algorithm 近似算法 1 每次任意选择一个未安排的工作，将它安排在当前负载最小的机器上 •这是一个 2倍近似算法 Approximation Algorithm 证明： 1. 2. 假设 Mi 是负载最大的机器，工作 j是机器 i最后一个工作，我们有： 1 amp。 amp。 m a xjj jjO P T t O