最小费用排序问题

Minimum Cost Sorting Problem

两类最小费用排序问题—费用函数满足三角不等式的最小费用排序问题和费用函数不满足三角不等式的最小费用排序问题.利用排序问题的O(nln(n))算法、图论和网络流理论分别给出了这两类问题的离线的最优多项式算法,并分别给出了这2个算法的最优性和计算复杂性分析.

In this paper, we consider two new types of sorting problems-Minimum cost sorting problem with cost function satisfies triangle inequality and minimum cost sorting problem without cost function does not satisfy triangle inequality. We give two optimal and polynomial off-line algorithms for them by using O （nln （n）） algorithm of sorting problem, and analyze their correctness and computational complexity.