问题1| d j = d |Σ w j T j 的一个全多项式近似方案

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1||Σ w j T j 的一个 O ( n 2 )时间的近似算法, 把该算法得到的目标值作为问题1| d j = d |Σ w j T j 的一个上界, 对问题1| d j = d |Σ w j T j 给出全多项式近似方案(FPTAS).已知问题1| d j = d |Σ w j T j 是一般意义下的NP-困难问题, 并且已经有人对该问题给出了拟多项式时间算法, 本文对已有结果进行了扩充.