使用聚類法對基因表達譜進行分析需要在方法上、理論上和算法上進一步研究，尋求突破。《若干聚類問題復雜性及其算法》由劉培強、李曙光、肖進傑所著，本書基於計算復雜性理論和基因表達譜分析理論，圍繞單向、雙向聚類問題某些形式未解決問題的復雜性證明、*高效的雙向聚算法的設計與開發、聚類算法的計算復雜度研究、求解缺失值算法的研究等展開，具體研究內容包括：（1）聚類分析求解算法；（2）未解決問題的復雜性；（3）在單向、雙向聚類方法中缺失數據的處理；（4）基因表達譜雙向聚類算法的性能評價。

聚類是指根據給定的多個對像及其屬性，基於相 似性函數度量對像間的相似性，以尋找有意義或有用 的對像分組。聚類分析方法是人們認識和理解世界的 最基本方式之一，廣泛應用於計算生物學、市場分析 、社交網絡數據分析、電子商務數據分析等眾多領域 。由於聚類分析的多樣性、重要性和廣泛性，尤其是 在目前大數據時代背景下，眾多應用領域對聚類分析 算法提出了新的挑戰。《若干聚類問題復雜性及其算 法》由劉培強、李曙光、肖進傑所著，《若干聚類問 題復雜性及其算法》從問題的計算復雜性證明和近似 算法設計的角度，對若干個聚類問題進行了討論和研 究，主要研究了帶缺失值的兩元指紋向量聚類問題、 兩元矩陣的k-子矩陣劃分問題、割聚類問題、設施定 位問題與k-median 問題等。本書可作為從事計算復 雜性理論、聚類分析研究和應用科技人員的參考書。

第1章 緒論 1
1.1 聚類分析 1
1.2 雙向聚類 3
1.2.1 雙向簇的類型 4
1.2.2 雙向聚類的解格式 5
1.3 數據矩陣上的聚類問題 6
1.4 兩元矩陣聚類問題 7
1.5 割聚類 8
1.6 設施定位問題和k-median問題 9
第2章 計算復雜性理論簡介 11
2.1 算法 11
2.2 計算模型 13
2.3 復雜性類 18
2.4 NP-**問題 20
2.5 NP-難問題 21
2.6 近似算法與啟發式算法 22
第3章 帶缺失值的基因表達譜聚類問題 29
3.1 問題的應用背景 29
3.2 問題的形式化描述 33
3.3 BCMV(2)問題的復雜性 34
3.3.1 零件圖及其性質 36
3.3.2 基於零件圖和X3C(3)實例構造圖G 37
3.3.3 由關聯圖構造BCMV(2)問題的實例 38
3.3.4 完成NP-難證明 42
3.4 求解BCMV問題的GCP算法 42
3.4.1 基於團劃分的啟發式算法 43
3.4.2 基於鏈表的GCP算法 45
3.4.3 基於鏈表的GCP算法實驗結果分析 50
3.4.4 經驗公式 54
3.5 基於線性規劃的求解算法 55
3.5.1 LAB算法 55
3.5.2 LAB算法的實驗結果及分析 59
3.6 本章小節 61
第4章 兩元矩陣的子矩陣劃分問題的復雜性及求解算法 62
4.1 引言 62
4.2 k-SPBM問題和k-PBB問題介紹 66
4.3 3-PBB問題是NP-**的 67
4.3.1 二分圖零件Ti1, Ti2, Ti3 69
4.3.2 由二分圖零件的MO3實例構造二分圖B 74
4.3.3 完成3-PBB的NP-**性證明 81
4.4 當k為大於3的正整數常量時，k-PBB (k＞3)問題的復雜性 83
4.5 k-SPBM問題的NP-**性證明 84
4.6 k-PBB問題求解算法 85
4.6.1 求解算法 85
4.6.2 算法分析 86
4.6.3 算法測試 87
4.7 本章小節 88
第5章 均衡負載聚類 90
5.1 問題的應用背景 90
5.2 引言 92
5.3 預備知識 93
5.4 鏈和環中的均衡負載聚類 93
5.5 樹和限制樹寬圖中的均衡負載聚類 95
5.6 本章小結 97
第6章 顏色相關*小負載聚類 98
6.1 引言 98
6.2 預備知識 99
6.3 仙人掌圖 100
6.4 參數為k的幾乎樹 103
6.5 本章小節 106
第7章 設施定位和k -median問題 107
7.1 相關概念和算法介紹 107
7.1.1 公制空間（Metric Space） 107
7.1.2 組合的生成算法 108
7.2 設施定位問題 108
7.2.1 基本概念 108
7.2.2 設施定位問題局部搜索算法 109
7.2.3 局部搜索算法的實現與求解實驗 115
7.2.4 局部搜索算法的改進 121
7.3 k-median問題 122
7.3.1 基本概念 122
7.3.2 k-median貪心近似算法 123
7.3.3 貪心算法近似度分析 124
7.3.4 貪心算法實驗數據 126
7.4 本章小節 128
本書符號說明 129
參考文獻 130