选址问题是运筹学领域的经典问题,在生产、物流管理、网络设计等实际问题中有非常广泛的应用.设施选址问题和k-中位问题是两个最基本的选址问题.这两个问题可以做为聚类问题,在数据挖掘领域发挥重要的作用.关联聚类是另一种聚类问题,适合类别个数未知的问题.这些问题都是NP-难的,在近似算法领域有大量的研究.本论文研究这些问题的重要变形,包括n次方度量的带线性惩罚的设施选址问题、带线性惩罚的k-设施选址问题、平方度量的k-设施选址问题、和带权图上的关联聚类问题.使用线性规划舍入、局部搜索、半定规划舍入等技术给出这些问题的近似算法和近似比的分析.在n次方度量的带线性惩罚的设施选址问题(简称MnFLPLP)中,顾客与设施的连接费用是n次方度量的(满足非负性、对称性、和n次方三角不等式).顾客如果未被任何设施服务,则需要付相应的惩罚费用.线性惩罚是指,一个可行解的惩罚费用等于每个顾客支付的惩罚费用之和.此问题是度量的设施选址问题的推广,因此也是NP-难的.我们将针对度量的带线性惩罚的设施选址问题的1.5148-近似算法应用到此问题上,并分析出近似比的隐式表达式.通过数值计算,给出n=2,…,10对应的常数近似比,以及n= 2和10对应的双因子近似比曲线,并与近似比的下界进行比较.我们发现n越小,近似比与其下界的间隙越小.另外,双因子近似比曲线与下界曲线在一定范围内也是非常接近的.在带线性惩罚的k-设施选址问题(k-FLPLP)中,顾客与设施的连接费用是度量的(满足非负性、对称性、和三角不等式),问题带有线性惩罚和设施的基数约束(即设施的开设个数不能超过给定的常数k).此问题是经典的设施选址问题与k-中位问题的一般化.因此是NP-难的.本论文将由添加,删除,和交换设施三种局部操作定义的局部搜索算法应用于k-FLPLP上.在算法的分析中,我们将“惩罚”视作虚拟设施,连接费用即为惩罚费用,以使对顾客的惩罚可以参与到局部操作的构造中.我们分析出算法的近似比与k-设施选址问题的相同,均为2 +(?)+ ε,说明对于这种局部搜索算法,惩罚费用没有对近似比造成影响.我们研究的第三种变形是平方度量的k-设施选址问题(简称SM-k-FLP).在此问题中,设施和顾客的位置在一个度量空间中,顾客与设施的连接费用等于两者距离的平方.与M2FLPLP的不同之处在于,SM-k-FLP没有惩罚费用,但是有设施的基数约束.这个问题是k-设施选址问题的一般化,所以也是NP-难的.我们使用局部搜索和放缩技术给出此问题的(22 +(?)+ε)-近似算法.通过数值实验,我们发现算法的实际效果很好.论文的最后一个研究问题是带权图上的关联聚类问题.在此问题中,每条边有两类权重,分别代表两端点的正、负相关性.我们需要将点集V进行聚类,目标是最大相同性,即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和.该问题是NP-难的,我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进,可以分析出依赖于实例的近似比.虽然不能将近似比0.75提高,但是对于大多数实例,近似比要好于0.75.