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