单机排序问题的数学规划表示

摘要：

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

关键词：排序、数学规划、指派问题

所属期刊栏目：14

分类号：O24(计算数学)

资助基金：国家自然科学基金19771057

在线出版日期：2007-05-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：77-82