基于半定規劃的多約束圖劃分問題

王曉瑜,劉紅衛,王 婷,丁玉婉,游海龍

(1.西安電子科技大學 數學與統計學院,西安 710126; 2.西安電子科技大學 微電子學院,西安 710071)

超大規模集成電路(VLSI)設計[1]、電信[2]和并行運算[3]等問題在數學建模時通常被抽象為圖的形式,圖分割是其基本算法之一.但隨著數據規模的不斷增長,圖劃分問題變得更具有多面性和挑戰性.該問題旨在將圖G=(V,E)的頂點在一定容量或基數的約束下劃分為幾個組,使得所求最優解的割邊總權重最小.由于該問題是NP-完備的,因此研究尋找近似解的方法有一定的意義.

圖劃分問題源于針對圖的k劃分問題設計的一個二次程序.隨著新的圖劃分問題的不斷發展,多種求解方法也應時而生,例如: Kernighan等[4]考慮將圖劃分為給定大小的子集,并設計了一種啟發式方法進行求解; Christofides等[5]對圖的二分問題提出了樹搜索方法,有效地限制了子集中節點的數目; Labbé等[6]針對團劃分問題,利用分支定界算法將圖劃分為有上下界的子集.

通過將圖劃分問題重新表述為一個非凸二次規劃問題,人們提出了一些有效的近似算法.Goemans等[7]對非負加權圖提出了基于半定松弛的舍入算法,該算法對k=2可實現0.878的近似界; Frieze等[8]針對圖的多分問題擴展了文獻[7]的舍入算法,并分析了所設計算法在不同劃分塊下的理論近似比.在近似算法的基礎上,分支定界法也被設計用于求解圖劃分問題.Rendl等[9]利用基于半定松弛的分支定界算法Biq Mac求解了經典的最大割問題; Delling等[10]根據分支……