课程大纲

课程大纲

组合优化选讲

课程编码:070105M07003H 英文名称:Selected Topics in Combinatorial Optimization 课时:20 学分:1.00 课程属性:高级强化课 主讲教师:徐大川

教学目的要求
(1) 要求掌握的基本知识
设施选址问题中的基础知识,聚类问题如k-means和k-median及次模优化的相关知识。
(2) 要求掌握的基本理论和方法
设计近似算法求解设施选址问题用到的线性规划、原始对偶、对偶拟合、局部搜索等技巧;
求解几类聚类问题所要用到的Lloyd、k-means++、k-means ||、局部搜索等方法;
求解基数约束下单调次模函数最大化问题的贪婪算法、流算法和并行算法。

预修课程
(1)线性规划 (2)组合优化

大纲内容
第一章 组合优化选讲 20学时
第1节 设施选址问题的算法设计与分析
第2节 k-median问题的算法设计与分析
第3节 k-means问题的算法设计与分析
第4节 次模函数最大化问题的算法设计与分析

参考书

课程教师信息