| 摘要 | 第4-5页 |
| abstract | 第5-6页 |
| 第一章 绪论 | 第9-17页 |
| 1.1 研究工作的背景与意义 | 第9-10页 |
| 1.2 国内外研究历史与现状 | 第10-15页 |
| 1.3 本文的主要贡献与创新 | 第15-16页 |
| 1.4 本论文的结构安排 | 第16-17页 |
| 第二章 线性规划基础 | 第17-31页 |
| 2.1 线性规划模型及其标准型 | 第17-18页 |
| 2.2 线性规划的几何意义 | 第18-21页 |
| 2.3 单纯形法 | 第21-24页 |
| 2.4 线性规划对偶理论 | 第24-28页 |
| 2.5 一类覆盖问题的整数规划模型 | 第28-30页 |
| 2.6 本章小结 | 第30-31页 |
| 第三章 混合支配问题的近似算法 | 第31-53页 |
| 3.1 问题介绍 | 第31-33页 |
| 3.2 一个简单的4倍近似算法 | 第33-38页 |
| 3.3 皇冠分解与NemhauserandTrotter定理 | 第38-45页 |
| 3.3.1 皇冠分解 | 第38-40页 |
| 3.3.2 NemhauserandTrotter定理 | 第40-45页 |
| 3.4 有关点覆盖问题的近似性质 | 第45-47页 |
| 3.5 点优先混合支配问题的一个3倍近似算法 | 第47-51页 |
| 3.6 本章小结 | 第51-53页 |
| 第四章 路径长度受限顶点多路割问题的近似算法 | 第53-63页 |
| 4.1 问题介绍 | 第53-54页 |
| 4.2 线性规划建模 | 第54-55页 |
| 4.3 一个L倍近似算法 | 第55-58页 |
| 4.4 一个近似率的下界 | 第58-60页 |
| 4.5 分离神谕与相关线性规划模型的求解 | 第60-61页 |
| 4.6 本章小结 | 第61-63页 |
| 第五章 全文总结与展望 | 第63-65页 |
| 5.1 全文总结 | 第63-64页 |
| 5.2 后续工作展望 | 第64-65页 |
| 致谢 | 第65-66页 |
| 参考文献 | 第66-71页 |
| 攻硕期间取得的研究成果 | 第71页 |