带下界约束的聚类问题的近似算法

韩璐，女，北京工业大学学士、博士，中国科学院数学与系统科学研究院博士后，现为北京邮电大学特聘副研究员，长期从事组合优化、近似算法方向的研究工作。

第1章绪论..

1.1经典的聚类问题

1.2聚类问题的重要变形....

1.2.1k-设施选址问题.....

1.2.2带背包约束的变形......

1.2.3奖励收集的变形...............1.2.4带容量约束的变形........1.2.5带下界约束的变形......

第2章带下界约束的k-中位问题....2.1问题介绍

2.2双标准近似算法..........

2.3基于归约过程的近似算法........2.4基于组合结构的近似算法....2.4.1 386-近似算法.....

2.4.2168-近似算法..

第3章广义的带下界约束的k-中位问题

3.1问题介绍.

3.2双标准近似算法..................3.3基于归约过程的近似算法.........

3.3.1转化和求解阶段............3.3.2构造可行解阶段..........

3.3.3主体算法及其结论......

3.4基于组合结构的近似算法........

第4章带下界约束的背包中位问题

4.1问题介绍

4.2双标准近似算法..

4.3基于归约过程的近似算法......4.4基于组合结构的近似算法.....

4.4.1751-近似算法........

4.4.2173-近似算法..........

第5章其他带下界约束的聚类问题

5.1最小最大r-聚集问题...............

5.1.13-近似算法......................

5.1.22-近似算法......

5.2最小求和r-聚集问题...........

5.3带下界约束的k-中心问题............

5.3.16-近似算法.....

5.3.22-近似算法.........

5.4奖励收集的带下界约束的k-中位问题.......5.5带弱下界约束的k-中位问题.........

参考文献

本书研究聚类问题带下界约束的模型，主要研究聚焦带下界约束的k-中位问题。第一章介绍k-中位问题以及相关聚类模型的研究背景。第二章介绍带下界约束的k-中位问题的现有近似算法。第三章介绍广义的带下界约束的k-中位问题的近似算法。第四章介绍带下界约束的k-中位问题的其他变形。第五章介绍其他带下界约束的聚类问题。