與最小查找的圖形分區邊線交叉分區

Question

我最近一直在幾個算法，並已經得到陷入以下問題：

給定一個無向加權可能斷開的圖G（V，E）發現的k個劃分G使得每個分區具有相同數量的頂點（假設頂點的總數是k的倍數）並且G中存在連接不同分區中的頂點的最少數量的邊。

我不想爲這個問題尋找一個多項式時間算法（因爲它可能是NP-Hard），而是一個算法，可以在24小時內找到150個頂點和1200個邊的解決方案。雖然任何好的近似算法都會受到高度讚賞，但我更喜歡精確的解決方案。

我保持這個問題儘可能簡單，但是一個有向加權圖的一般解決方案也會很好。

感謝您的幫助！

更新：我只是做了一些更多的研究，並意識到這可以重新解釋爲一個修改的連接問題。也許沿着這個思路有一個解決方案？

Answer 1

這確實是一個NP難題。如果你使用凸優化或者可以學習，我的直覺就是將這個問題表達爲具有許多變量的exact coverinteger program（每個子集的| V |/k個頂點一個），然後通過generating columns用一個整數程序求解器找到有許多內部邊緣的分區。子問題制定的樣子

maximize sum_{vertices v} w_v x_v + sum_{edges uv} y_{uv} 
subject to 
sum_{vertices v} x_v = |V|/k 
y_{uv} <= x_u for all edges uv 
y_{uv} <= x_v for all edges uv 
x_v in {0, 1} for all vertices v 
y_{uv} in {0, 1} for all edges uv 

其中w_v由雙解到主問題設定的權重，直觀地理解爲一個特定的頂點是如何迫切需要覆蓋。

Answer 2

一種方法是使用聚類算法。你不會得到最佳的解決方案，而是一個快速的半優化解決方案。

你可以通過各種方式來解決這個問題。例如，你可以使用biclustering。或者你可以做主成分分析，挑選一些組件並運行修改的k-means算法。