k-均值问题是经典组合优化问题，也是著名的NP-难问题之一，相应的Lloyd算法是数据挖掘的十大经典算法之一、k-均值问题在人工智能、数据挖掘、理论计算机科学、运筹学和管理科学中有着广泛的应用。本书介绍k-均值问题及其变形的基于随机抽样、降维、核心集、近似质心集、局部搜索、线性规划舍入等技术的近似算法，主要内容包括：经典k-均值问题的近似算法，k-中位，球面k-均值，鲁棒k-均值，带约束的k-均值，隐私保护k-均值，k-均值的其他变形等。
本书可作为运筹学、统计学、计算机科学、管理科学和应用数学专业的高年级本科生和研究生的教材和参考书，亦可作为相关研究领域科研人员的参考书。

第1章 绪论
1.1 k-均值问题
1.2 k-均值问题的重要变形
1.2.1 k-中位问题
1.2.2 球面k-均值问题
1.2.3 鲁棒k-均值/中位问题
1.2.4 带约束的k-均值问题
1.2.5 隐私保护k-均值问题
1.2.6 泛函k-均值问题
1.2.7 模糊C-均值问题
1.2.8 其他变形
第2章 k-均值初始化方法
2.1 k-均值++算法
2.1.1 算法设计
2.1.2 算法分析
2.1.3 下界
2.2 k-均值｜｜算法
2.2.1 并行算法设计
2.2.2 并行算法分析
第3章 Johnson-Lindenstrauss降维引理
3.1 预备知识
3.1.1 基本概念
3.1.2 Brunn-Minkowski不等式
3.2 高维空间及其特性
3.2.1 超球体的几何特性
3.2.2 高维空间的概率集中性
3.3 随机投影定理和Johnson-Lindenstrauss降维引理
3.3.1 随机投影定理
3.3.2 Johnson-Lindenstrauss降维引理
第4章 核心集与近似质心集
4.1 核心集
4.1.1 问题描述
4.1.2 核心集构造算法
4.1.3 核心集结论的证明
4.2 ε-近似质心集
4.2.1 ε-近似质心集的定义和性质
4.2.2 整数格上的k-均值问题
4.2.3 稀疏实例
4.2.4 一般实例
第5章 k-中位和k-均值问题的局部搜索算法
5.1 k-中位问题的局部搜索算法
5.1.1 问题描述
5.1.2 单交换局部搜索算法
5.1.3 简单情形的局部比值
5.1.4 一般情形的局部比值
5.1.5 多项式时间近似算法
5.1.6 多交换局部搜索算法
5.2 k-均值问题的局部搜索算法
5.2.1 单交换局部搜索算法
5.2.2 多交换局部搜索算法
第6章 k-均值问题的双准则近似算法
6.1 线性规划舍入算法
6.2 局部搜索算法
第7章 有序k-中位问题
7.1 问题描述
7.2 近似算法
7.2.1 算法框架
7.2.2 矩形有序k-中位问题的近似比分析
7.2.3 一般有序k-中位问题的近似比分析
第8章 球面k-均值问题
8.1 问题描述
8.1.1 概述
8.1.2 性质
8.2 球面k-均值问题的初始化算法
8.2.1 问题描述
8.2.2 可分离球面k-均值问题的近似初始化算法
8.2.3 推广的球面k-均值问题的近似算法
8.3 局部搜索算法
8.3.1 单交换的局部搜索算法
8.3.2 多交换的局部搜索算法
第9章 鲁棒k-均值问题
9.1 带惩罚的k-均值问题
9.1.1 概述
9.1.2 单交换局部搜索算法
9.1.3 多交换局部搜索算法
9.2 带惩罚k-中位/均值问题局部搜索算法
9.2.1 问题描述
9.2.2 算法及分析
9.3 带异常点k-中位/均值问题局部搜索算法
9.3.1 问题描述
9.3.2 算法描述
9.3.3 近似比分析
第10章 带约束k-均值问题
10.1 问题描述
10.2 带约束k-均值问题的剥离封闭算法
10.2.1 单纯形引理
10.2.2 剥离封闭算法
10.2.3 剥离封闭算法分析
10.3 带约束k-均值问题的选择算法
10.3.1 下界约束后.均值问题的选择算法
10.3.2 r-容量约束k-均值问题的选择算法
10.3.3 色谱k-均值问题的选择算法
第11章 其他变形
11.1 隐私保护k-均值
11.1.1 差分隐私概念
11.1.2 差分隐私k-均值问题描述
11.1.3 差分隐私常用的机制
11.1.4 高维差分隐私k-均值问题
11.2 泛函k-均值问题
11.2.1 问题描述
11.2.2 泛函k-均值问题的初始化算法
11.3 模糊C-均值问题
11.3.1 问题描述
11.3.2 模糊C-均值问题的初始化算法
11.4 平方和设施选址问题
11.4.1 问题描述
11.4.2 连续SOS-FLP的局部搜索算法
11.4.3 离散SOS-FLP的局部搜索算法
11.5 带惩罚μ-相似Bregman散度k-均值问题
11.5.1 问题描述
11.5.2 带惩罚μ-相似Bregman散度K-均值问题的初始化算法
参考文献
名词索引