第 1 章  緒論    1
1.1  k-均值問題  1
1.2  k-均值問題的重要變形    7
1.2.1  k-中位問題    7
1.2.2  球面 k-均值問題  8
1.2.3  魯棒 k-均值/中位問題  9
1.2.4  帶約束的 k-均值問題  11
1.2.5  隱私保護 k-均值問題  12
1.2.6  泛函 k-均值問題    13
1.2.7  模糊 C-均值問題  13
1.2.8  其他變形  14
第 2 章  k-均值初始化方法  15
2.1  k-均值 算法  15
2.1.1  算法設計  16
2.1.2  算法分析  16
2.1.3  下界    25
2.2  k-均值 || 算法  27
2.2.1 並行算法設計  27
2.2.2 並行算法分析  28
第 3 章  Johnson-Lindenstrauss 降維引理  35
3.1  預備知識    35
3.1.1  基本概念  35
3.1.2  Brunn-Minkowski 不等式  36
3.2  高維空間及其特性  36
3.2.1  超球體的幾何特性    37
3.2.2  高維空間的概率集中性   38
3.3  隨機投影定理和 Johnson-Lindenstrauss 降維引理    40
3.3.1  隨機投影定理  40
3.3.2  Johnson-Lindenstrauss 降維引理    42
第 4 章  核心集與近似質心集  45
4.1  核心集   45
4.1.1  問題描述  45
4.1.2  核心集構造算法    47
4.1.3  核心集結論的證明    49
4.2  -近似質心集    53
4.2.1  -近似質心集的定義和性質. 54
4.2.2  整數格上的 k-均值問題  55
4.2.3  稀疏實例  57
4.2.4  一般實例  61
第 5 章  k-中位和 k-均值問題的局部搜索算法    67
5.1  k-中位問題的局部搜索算法    67
5.1.1  問題描述  67
5.1.2  單交換局部搜索算法    68
5.1.3  簡單情形的局部比值    68
5.1.4  一般情形的局部比值    78
5.1.5  多項式時間近似算法    80
5.1.6  多交換局部搜索算法    83
5.2  k-均值問題的局部搜索算法    87
5.2.1  單交換局部搜索算法    87
5.2.2  多交換局部搜索算法    91
第 6 章  k-均值問題的雙準則近似算法    95
6.1  線性規劃舍入算法  95
6.2  局部搜索算法 106
第 7 章  有序 k-中位問題  113
7.1  問題描述  113
7.2  近似算法  114
7.2.1  算法框架    114
7.2.2  矩形有序 k-中位問題的近似比分析 116
7.2.3  一般有序 k-中位問題的近似比分析 123
第 8 章  球面 k-均值問題  127
8.1  問題描述  127
8.1.1  概述  127
8.1.2  性質  129
8.2  球面 k-均值問題的初始化算法    132
8.2.1  問題描述    132
8.2.2  可分離球面 k-均值問題的近似初始化算法  133
8.2.3  推廣的球面 k-均值問題的近似算法 140
8.3  局部搜索算法 142
8.3.1  單交換的局部搜索算法   142
8.3.2  多交換的局部搜索算法   148
第 9 章  魯棒 k-均值問題  152
9.1  帶懲罰的 k-均值問題  152
9.1.1  概述  152
9.1.2  單交換局部搜索算法  152
9.1.3  多交換局部搜索算法  158
9.2  帶懲罰 k-中位/均值問題局部搜索算法    162
9.2.1  問題描述    163
9.2.2  算法及分析    163
9.3  帶異常點 k-中位/均值問題局部搜索算法  171
9.3.1  問題描述  171
9.3.2  算法描述  172
9.3.3  近似比分析    173
第 10 章  帶約束 k-均值問題    181
10.1  問題描述    181
10.2  帶約束 k-均值問題的剝離封閉算法   183
10.2.1  單純形引理  184
10.2.2  剝離封閉算法  188
10.2.3  剝離封閉算法分析  190
10.3  帶約束 k-均值問題的選擇算法  197
10.3.1  下界約束 k-均值問題的選擇算法  197
10.3.2  r -容量約束 k-均值問題的選擇算法  198
10.3.3 色譜 k-均值問題的選擇算法  198
第 11 章  其他變形    199
11.1  隱私保護 k-均值  199
11.1.1  差分隱私概念    199
11.1.2  差分隱私 k-均值問題描述   200
11.1.3  差分隱私常用的機制   201
11.1.4  高維差分隱私 k-均值問題   202
11.2  泛函 k-均值問題  206
11.2.1  問題描述  206
11.2.2  泛函 k-均值問題的初始化算法  209
11.3  模糊 C-均值問題  211
11.3.1  問題描述  211
11.3.2  模糊 C-均值問題的初始化算法. 214
11.4  平方和設施選址問題  217
11.4.1  問題描述  217
11.4.2  連續 SOS-FLP 的局部搜索算法   221
11.4.3  離散 SOS-FLP 的局部搜索算法   231
11.5  帶懲罰 -相似 Bregman 散度 k-均值問題    234
11.5.1  問題描述  234
11.5.2  帶懲罰-相似 Bregman 散度 k-均值問題的初始化算法  236
參考文獻  247
名詞索引  259

??

??

??

近十幾年來,  k-均值問題在運籌學、統計學和計算機科學 (包括人工智能、數據挖掘、 理論計算機科學、離散幾何等) 得到了廣泛關注. 人們在 k-均值問題的近似算法領域取得了非常豐富的研究成果. 
本書第 1 章是緒論, 主要介紹問題模型與結果. 第 2 章介紹 k-均值初始化方法. 第3 章和第 4 章分別介紹 Johnson-Lindenstrauss 降維引理、核心集與近似質心集, 為後面兩章設計近似算法提供準備工作. 第 5 章介紹 k-中位和k-均值問題的局部搜索算法. 第6 章介紹 k-均值問題的雙準則近似算法. 第 7 章至第 11 章介紹 k-均值問題的各種變形. 書中 1.1～1.2 節, 9.1～9.3 節, 10.1～10.4 節, 12.2～12.5 節是作者與合作者近年來的研究成   果[139, 141, 145, 146, 181, 193–196]. 其他章節取材於文獻 [16, 19, 26, 27, 32, 46, 78, 93, 94, 107, 113, 126, 153, 156, 185]. 
本書部分內容曾在北京工業大學運籌學專業的近似算法課程和研究生討論班中講授. 感謝我們的學生褚天舒、姬賽、劇嘉琛、連月芳、劉文傑、劉文釗、劉治成、盧茂文、生瑞琦、孫建、孫悅、田曉雲、吳晨晨、肖昊、許宜誠、楊龍千、楊瑞琪、袁藩錄入部分內容並校對初稿, 其中褚天舒和孫悅付出了很多時間和精力. 感謝我們的朋友和同事陳旭瑾、郭龍坤、韓鑫、李偉東、劉茜、葉德仕、張國川、張鵬、張曉岩、張湧、張玉忠、張昭等對本書初稿提出的寶貴建議和修改意見. 
感謝中國科學院數學與繫統科學研究院韓繼業研究員、袁亞湘研究員、胡曉東研究員, 山東大學計算機科學與技術學院馬軍教授、朱大銘教授, 山東師範大學數學與統計學院王江魯教授, 科英布拉大學數學繫 Luis Nunes Vicente 教授, 得克薩斯大學達拉斯分校計算機繫堵丁柱教授等多年來對作者的支持和幫助. 感謝山東建築大學計算機科學與技術學院、山東師範大學數學與統計學院、北京工業大學理學部為我們提供的良好科研環境. 此外, 作者要感謝各自的家人對我們工作的支持和理解. 特別地, 本書作者的父親曲阜師範大學運籌學研究所副所長張慶水教授在此書付梓之際離開了這個世界, 他生前對作者的諄諄教誨, 言猶在耳, 謹以此書獻給他. 
本書得到山東建築大學計算機科學與技術學院學位點建設專項資金、國家自然科學基金 (No. 11871081) 的資助. 
由於作者水平有限, 本書難免有錯誤和不妥之處, 歡迎讀者批評指正. 

張鼕梅  李 敏  徐大川 
山東建築大學 山東師範大學 北京工業大學 
2022 年 5 月 4 日