| 摘要 | 第1-6页 |
| ABSTRACT | 第6-9页 |
| 第一章 绪论 | 第9-15页 |
| §1.1 应用背景及问题描述 | 第9-12页 |
| §1.1.1 应用背景 | 第9页 |
| §1.1.2 经典排序与现代排序 | 第9-10页 |
| §1.1.3 三参数表示法 | 第10-12页 |
| §1.2 预备知识 | 第12-14页 |
| §1.3 本文主要结果及创新点 | 第14-15页 |
| 第二章 一个可拒绝分批排序的NP-困难性的证明 | 第15-21页 |
| §2.1 问题背景及研究现状 | 第15-16页 |
| §2.2 问题描述及相关符号 | 第16页 |
| §2.3 问题NP-困难性的证明 | 第16-20页 |
| §2.4 结论 | 第20-21页 |
| 第三章 一个可拒绝分批排序的动态规划算法和近似算法 | 第21-27页 |
| §3.1 动态规划算法 | 第21-24页 |
| §3.2 2-近似算法 | 第24-25页 |
| §3.3 完全多项式时间近似算法 | 第25-26页 |
| §3.4 结论 | 第26-27页 |
| 参考文献 | 第27-30页 |
| 附录一 攻读硕士期间撰写的论文 | 第30-31页 |
| 附录二 致谢 | 第31页 |