课程概述
算法设计与分析专题之近似算法。
证书要求
证书规则将在开课前发布
预备知识
集合论图论，高等数学，数据结构与算法。
授课大纲
算法设计与分析之近似算法篇
第一周 近似算法概述
1-1 NP-完全问题
1-2 性能比
1-3 近似算法的例子
第二周 贪心法
2-1 独立系统与拟阵
2-2 独立集合问题
2-3 次模函数
2-4 加权集合覆盖问题
第三周 限制法
3-1 Steiner树问题
3-2 k-限制Steiner树问题
3-3 最小生成树
第四周 松弛法
4-1 松弛概述
4-2超串问题
4-3 LP-松弛
第五周 拟合与对偶
5-1 对偶概述
5-2 集合覆盖的对偶分析
5-3 最大可满足性
第六周 不可近似性
6-1 不可近似性的证明
6-2 旅行商问题
6-3 背包问题
6-4 L-归约
参考资料
殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志 (译). 算法导论. 机械工业出版社, 2012. 12.
