| 摘要 | 第1-12页 |
| ABSTRACT | 第12-14页 |
| 第一章 绪论 | 第14-36页 |
| ·NP难解最优化问题 | 第15-16页 |
| ·近似算法 | 第16-24页 |
| ·标准近似 | 第16-21页 |
| ·微分近似 | 第21-22页 |
| ·占优分析 | 第22-24页 |
| ·旅行商问题研究现状概述 | 第24-26页 |
| ·最大覆盖圈包装相关问题研究现状概述 | 第26-33页 |
| ·独立路径问题 | 第26-29页 |
| ·圈包装问题 | 第29-32页 |
| ·路圈子图问题 | 第32页 |
| ·最大覆盖圈包装问题 | 第32-33页 |
| ·研究问题的提出 | 第33-34页 |
| ·文章结构与主要工作 | 第34-36页 |
| 第二章 曲面上旅行商问题的多项式时间近似方案 | 第36-54页 |
| ·引言 | 第36-38页 |
| ·相关近似方案 | 第36-37页 |
| ·思路与结论 | 第37-38页 |
| ·曲面上 TSP 的 NP难解性 | 第38-39页 |
| ·球面上 TSP 的多项式时间近似方案 | 第39-50页 |
| ·球面的两个性质 | 第39-42页 |
| ·球面上小尺度 TSP 实例的多项式时间近似方案 | 第42-49页 |
| ·球面上一般 TSP 实例的多项式时间近似方案 | 第49-50页 |
| ·曲面上 TSP 具有多项式时间近似方案的充分条件 | 第50-52页 |
| ·小结 | 第52-54页 |
| 第三章 曲面上的旅行商问题常数 | 第54-72页 |
| ·引言 | 第54-57页 |
| ·曲面上的 TSP 常数 | 第57-63页 |
| ·动机 | 第57-58页 |
| ·构造 | 第58-63页 |
| ·一般曲面上的 TSP 常数 | 第63页 |
| ·TSP 常数的一个新解释 | 第63-64页 |
| ·数值实验 | 第64-68页 |
| ·实验设置 | 第64页 |
| ·正方形实验 | 第64-65页 |
| ·采样次数影响之实验 | 第65-66页 |
| ·球面实验 | 第66-68页 |
| ·正方体实验 | 第68页 |
| ·小结 | 第68-72页 |
| 第四章 制服调换问题的线性时间算法 | 第72-90页 |
| ·引言 | 第72-73页 |
| ·制服调换问题 | 第73-74页 |
| ·以物易物的制服调换 | 第74-84页 |
| ·两两交换 | 第75-76页 |
| ·自由调换 | 第76-83页 |
| ·带库存的自由调换 | 第83-84页 |
| ·一般制服调换和以物易物的制服调换的比较 | 第84-87页 |
| ·UE、BUE 最优解之间的关系 | 第84页 |
| ·UE、BUE 最优解实验 | 第84-87页 |
| ·小结 | 第87-90页 |
| 第五章 肾脏调换问题：模型与算法 | 第90-104页 |
| ·引言 | 第90-92页 |
| ·偏好列表模型 | 第92-94页 |
| ·多捐赠者情形下的偏好列表模型 | 第94-101页 |
| ·解的结构 | 第96-98页 |
| ·扩展 TTC 算法 | 第98-100页 |
| ·稳定解的难解性 | 第100-101页 |
| ·实验 | 第101-102页 |
| ·小结 | 第102-104页 |
| 第六章 结束语 | 第104-106页 |
| 致谢 | 第106-108页 |
| 参考文献 | 第108-128页 |
| 作者在学期间取得的学术成果 | 第128-130页 |
| 附录A 数学概念及符号 | 第130-133页 |
| A.1 图论 | 第130-132页 |
| A.2 组合 | 第132页 |
| A.3 分析 | 第132-133页 |
| A.4 其它 | 第133页 |