聚类问题是计算机科学和运筹学领域中的经典问题,具有广泛的实际应用背景.本论文通过设计近似算法,对球面k-平均问题,设施选址问题和关联聚类问题三种聚类问题的变形进行研究.主要研究内容为:带惩罚的球面k-平均问题,带惩罚的容错施选址问题,两阶段随机容错设施选址问题、不确定关联聚类问题以及容量约束关联聚类问题.文章基于线性舍入技巧、初始化技巧和贪婪增广设计上述变形问题的近似算法并给出相应的理论分析.在带惩罚的球面k-平均问题中:给定分布在单位球面上的数据点的集合,正整数k,每个点的惩罚费用以及两点之间的距离,每个数据点可以被聚类也可以被惩罚.问题的目标是区分被惩罚的点和被聚类的点并将被聚类的点分成k类,使得被聚类的点到其对应中心的距离的和与总的惩罚费用的和最小.模型的提出有效的避免了个别点对整体造成过度的影响.该问题的难点在于如何选择k个中心点使得可以从理论的角度来分析算法的好坏.我们首先基于初始化技巧对一般实例给出了 2Mmax{2,M}(1+M)(lnk+2)-近似算法.其次证明了对于可分实例,算法以概率[(4max{5,M+1})1-k]/2实现近似比2max{3,M+1},其中M为实例中最大的惩罚费用与最小惩罚费用的比值.在带惩罚的容错设施选址问题中,给定设施的集合,顾客的集合,设施的开设费用以及顾客与设施之间连接费用,每个顾客的连接需求及其权重向量和惩罚费用的向量.顾客的每个需求可以被连接在一个开设的设施上也可以通过支付对应的惩罚费用被拒绝.目标是挑选一些设施开设,拒绝部分顾客的部分需求并满足剩下的顾客的需求来极小化总的设施费用,带权的连接费用以及惩罚费用的和.模型的提出有效的避免了个别点对整体造成过度的影响.在本论文中我们利用线性舍入技巧来设计近似算法,该技巧的难点在于分数最优解并不能很好的反应解的结构从而很难识别被惩罚的顾客.为了克服这一难点,我们首先在分数最优解的基础上构造了一个费用不增加但能较好的反应解的结构的分数可行解.其次在构造的分数可行解的基础上通过引入待定参数来识别被惩罚的顾客.最终通过一定的技巧来选择开设的设施来得到整数可行解.我们证明了该算法是4-近似的确定的算法并进一步利用随机舍入的技巧将近似比改进到3.16,最终通过贪婪增广技巧将近似比改进到2.408.在两阶段随机容错设施选址问题中,给定设施的集合和顾客的集合,设施在两个阶段的开设费用以及设施与顾客之间的连接费用,K个不同的场景对应的顾客集合及其概率分布,每个场景下顾客需要连接的设施的个数及其权重向量.设施的开设分为两个阶段,第一个阶段中开设的设施可以服务所有场景下的顾客,第二个阶段下针对不同场景开设的设施只能服务对应场景下的顾客.目标是分两个阶段开设设施并且保证每个场景下的顾客都能连接在一定数目的开设的设施上来极小化第一阶段的设施费用和K个场景下设施费用和带权得连接费用的期望.模型的提出有效的克服了单一变形无法刻画实际问题的局限性.论文基于线性舍入技巧计近似算法,该技巧的难点在于分数最优解并不能反映解的结构.为了克服这一难点,我们在分数最优解的基础上构造了一个可以更好反应解的结构的分数可行解.在本论文中,我们利用上述技巧得到5-近似的确定的算法并进一步利用随机舍入的技巧将近似比改进到3.8617.在不确定关联聚类问题中,给定完全图以及每条边成为正边的概率.问题的目标是将图中的顶点分为若干类来极小化两个顶点在不同类的正边以及两个顶点在同一个类的负边的个数的期望.该模型的提出有效的克服了当前的算法只能处理确定图上的关联聚类问题的局限性.论文利用线性舍入技巧来设计近似算法,该技巧的难点在于如何基于分数最优解来识别出应当被聚到一类里的点的集合.为了克服这一难点,我们引入待定参数给出了一个聚类的准则,并通过恰当的选取参数得到了 6-近似的算法.在容量约束关联聚类问题中,给定完全图G=(V,E),其中V是顶点的集合,E是边的集合.每条边根据其关联的顶点的相似性有一个标号+或-.每个顶点v∈V对应了正整数Uv.目标是将顶点分为若干类来极小化标号为+且两个顶点在不同类里的边和标号为-且两个顶点在同一类里的边的个数和.并且算法输出任何类C满足|C| ≤minv∈CUv.本论文利用线性舍入技巧来设计近似算法,我们首先基于待定参数α∈(0,1/2]给出了(1/(1-α),2/α)-双准则近似算法,即算法输出的解对应的目标函数值不超过最优解的2/α倍且算法输出的每个聚类C满足|C| ≤minv∈CUv/(1-α)其次我们通过限制每个类里顶点的个数给出了2U-近似的算法,其中U=maxv∈VUv.