| 摘要 | 第1-7页 |
| Abstract | 第7-11页 |
| 第1章 引言 | 第11-15页 |
| ·组合优化 | 第11-12页 |
| ·通讯网络中的组合优化 | 第12页 |
| ·环上路由问题 | 第12-13页 |
| ·本文的主要结构 | 第13-15页 |
| 第2章 一些概念和结论 | 第15-23页 |
| ·复杂性理论的基本概念 | 第15-16页 |
| ·NP-最优化问题和近似算法 | 第16-18页 |
| ·多商品流和边不相交的路 | 第18-23页 |
| 第3章 环上路由问题及其发展现状 | 第23-31页 |
| ·介绍 | 第23-24页 |
| ·环负载问题 | 第24-26页 |
| ·逆向旋转环上的负载平衡路由问题 | 第26-27页 |
| ·节点容量有限的环上路由问题 | 第27-31页 |
| 第4章 有负载限制的逆向旋转环上的路由问题 | 第31-41页 |
| ·模型和符号 | 第31-32页 |
| ·多项式时间算法 | 第32-39页 |
| ·LRRR 的线性规划松弛 | 第33-34页 |
| ·平行路由 | 第34-35页 |
| ·半不可分路由 | 第35-37页 |
| ·不可分路由 | 第37-39页 |
| ·结论 | 第39-41页 |
| 参考文献 | 第41-44页 |
| 致谢 | 第44-45页 |
| 攻读硕士学位期间完成的文章 | 第45页 |