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