论文标题
通过预测分区：大图分区问题的强大SDP界限
Partitioning through projections: strong SDP bounds for large graph partition problems
论文作者
论文摘要
图分区问题（GPP）旨在将图的顶点集聚类到给定尺寸的固定数量的差异子集中，以便最小化连接不同集合的边缘的权重。本文研究了双重不负（DNN）松弛的质量，即具有矩阵变量的放松既是矩阵变量既是阳性半菲尼特和非负的，又通过额外的多面体切割来增强GPP：$ k $ - $ - 额定设备和图形双分配问题的两种变体。通过面部减少减少松弛的大小后，我们通过将增强的拉格朗日方法与Dykstra的投影算法相结合的切削平面算法来解决它们。由于我们的算法的许多组件都是一般的，因此该算法适用于用大量切割平面求解各种DNN松弛。我们是第一个在最高1,024个顶点的大型基准实例上使用额外的GPP切割平面来展示DNN松弛力量的人。计算结果显示出加强的DNN界限的令人印象深刻的改善。
The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both positive semidefinite and nonnegative, strengthened by additional polyhedral cuts for two variations of the GPP: the $k$-equipartition and the graph bisection problem. After reducing the size of the relaxations by facial reduction, we solve them by a cutting-plane algorithm that combines an augmented Lagrangian method with Dykstra's projection algorithm. Since many components of our algorithm are general, the algorithm is suitable for solving various DNN relaxations with a large number of cutting planes. We are the first to show the power of DNN relaxations with additional cutting planes for the GPP on large benchmark instances up to 1,024 vertices. Computational results show impressive improvements in strengthened DNN bounds.
