關聯聚類問題的半定規劃舍入算法
摘要：主要研究帶有兩類權重的一般圖下的關聯聚類問題. 問題的定義是, 給定圖G=（V,E）, 每條邊有兩類權重, 我們需要將點集V進行聚類, 目標是最大相同性, 即最大化屬于某個類的邊的第一類權重之和加上在兩個不同類之間的邊的第二類權重之和. 該問題是NP-難的, 我們利用外部旋轉技術將現有的半定規劃舍入0.75-近似算法改進. 算法的分析指出, 改進的算法雖然不能將近似比0.75提高, 但是對于大多數實例, 可以獲得更好的運行效果.
注: 保護知識產權,如需閱讀全文請聯系運籌學學報雜志社
相關推薦
更多
