本书主要介绍几个与排序(scheduling)和集合覆盖(set covering)问题相关的近似算法及其分析。排序和集合覆盖问题，均是组合优化领域中经典的问题。一般而言，排序指的是：给定机器和待加工的工件，对工件制订一个在机器上加工的计划，使得所有工件尽可能快地完工。集合覆盖指的是：给定一个元素集以及由该元素集合中元素组成的备选集合族，选择合适的子集合，使得所有的元素均包含在所选子集合中，这种包含关系被称为覆盖。随着人们对这两个问题研究的深入，与之相关的更为复杂的问题也被清晰地刻画出来，成为更贴合实际的研究热点。它们不但具有很高的理沦价值，更具有非常广泛的应用背景。本书主要研究了排序博弈(scheduling game)、旅行商问题(TSP)和覆盖约束排序(scheduling with covering constraints)、连通集合覆盖问题及3路点覆盖问题(VCP3)，并分别对这些问题设计了相关算法且加以算法分析。

第1章 绪论
1.1 基础知识
1.2 研究的问题
1.3 研究背景与研究现状
1.4 本章小结
第2章 两个代理人单机排序博弈中公平的代价问题
2.1 预备知识
2.2 问题□(数理化公式)的POFks
2.3 本章小结
第3章 m-Steiner旅行商问题的渐近紧在线算法
3.1 预备知识
3.2 MinMax-mSTSPonline问题的下界
3.3 MinMax-mSTSPonline问题的在线算法及其分析
3.4 本章小结
第4章 覆盖约束下的平行机排序问题
4.1 预备知识
4.2 任意数量变速机Rm|SC|Cmax
4.3 任意数量同速机Pm|SC|Cmax
4.4 固定数量同速机Pm|SC|Cmax
4.5 固定数量变速机Rm|SC|Cmax
4.6 本章小结
第5章 r-hop条件下的最小赋权部分连通集合覆盖问题
5.1 r-hop条件下的最小赋权部分连通集合覆盖问题
5.2 r-hop条件下的最小部分连通集合覆盖问题
5.3 本章小结
第6章 3-路点覆盖的在线算法
6.1 预备知识
6.2 算法及其分析
6.3 紧例子
6.4 本章小结
第7章 总结与展望
主要参考文献