排序问题的高性能算法

研究具有重要应用价值的排序问题。对其中的NP困难离线问题，探讨多项式时间近似方案的存在性并设计真正实用的快速近似优算法；对在线半在线问题，设计具有最好近似性能比的算法。我们还考虑随机化方法在这些问题上的应用，期望得到在时间复杂性或性能比上较已有的确定型算法更好的算法。