加急见刊

关联聚类问题的半定规划舍入算法

王一水; 徐大川; 吴晨晨 北京工业大学应用数理学院; 北京100124; 天津理工大学理学院; 天津300384

摘要：主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=（V,E）, 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.

注: 保护知识产权,如需阅读全文请联系运筹学学报杂志社