| 摘要 | 第1-4页 |
| Abstract | 第4-7页 |
| 第1章 引言 | 第7-13页 |
| 第2章 P_m|vertex cover|C_(max) | 第13-33页 |
| ·对P_m|vertex cover|C_(max)问题的3=2/(m+1)近似算法 | 第14-18页 |
| ·对P_m|vertex cover|C_(max)问题的进一步的算法 | 第18-26页 |
| ·对P_m|hitting set|C_(max)的近似算法 | 第26-33页 |
| 第3章 P_m|covering|C_(max)，Q_m|covering|C_(max) | 第33-45页 |
| ·算法与初步分析 | 第35-37页 |
| ·对Q_m|covering|C_(max)的(r+(m-1)λ_m/(∑_(i=1)~mλ_i)近似算法 | 第37-39页 |
| ·对P_m|X|C_(max)的近似算法 | 第39-43页 |
| ·算法与分析 | 第39-41页 |
| ·应用 | 第41-43页 |
| ·P_m|Shortest Path|C_(max) | 第41-42页 |
| ·P_m|Prize Collecting Vertex Cover|C_(max) | 第42-43页 |
| ·P_m|Hitting Set|C_(max) | 第43页 |
| ·说明 | 第43-45页 |
| 第4章 P_m|packing|C_(min)，Q_m|packing|C_(min)，Q2|packing|C_(min) | 第45-59页 |
| ·对Q_m|packing problem|C_(min)的近似算法 | 第48-53页 |
| ·算法 | 第48-50页 |
| ·算法的时间复杂度 | 第50-52页 |
| ·算法的最坏情形比 | 第52-53页 |
| ·进一步的结论 | 第53-59页 |
| ·对P_m|packing problem|C_(min)问题的进一步结论 | 第53-54页 |
| ·对Q_2|Packing|C_(min)问题的进一步算法 | 第54-59页 |
| 第5章 总结 | 第59-60页 |
| 参考文献 | 第60-63页 |
| 致谢 | 第63-66页 |
| 个人简历、在学期间发表的学术论文与研究成果 | 第66页 |
