论文部分内容阅读
本文把单机排序问题1||∑wjCj表述成一个二次规划，并把不带权的问题1||∑Cj进一步转化成指派问题，从而用指派问题的匈牙利算法证明SPT序是问题1||∑Cj的最优解，这个结论似乎很平凡，但对于用数学规划来研究排序问题是一个很有意义的进展，这为我们用二次规划和半定规划来研究NP困难的排序问题的近似算法打下基础。