论文标题
为顶点覆盖问题的上层平面算法和溶液增白
Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
论文作者
论文摘要
在随机图的集合上，通过线性编程（LP）研究了NP-HARD顶点覆盖（VC）组合优化问题的相变行为。由于适用于此类LP的基本单纯形（SX）算法可能会产生不完整的解决方案以进行足够复杂的图形，因此寻求切割平面（CP）方法的应用。我们考虑Gomory和{0,1/2}剪切。我们测量使用这些方法作为平均节点C度C的函数获得完整溶液的概率，并观察到通常完整和不完整相位区域之间的过渡。尽管对于任意高复杂性的图表，通常无法获得不完整的解决方案，但与纯SX算法相比，CP方法仍然超出了C = E = E = 2.718 ...的已知复制对称性破坏（RSB）的跃迁。实际上，我们的结果为C = 2.90（2）的另一种算法过渡提供了证据。 除此之外，我们还根据数值努力量化了VC问题的简易解决性和硬溶性之间的过渡。此外，我们研究了溶液的所谓美白，这是单个顶点在退化溶液方面经历的自由度的衡量标准。检查与白色顶点簇相关的数量的检查表明，RSB过渡仅略微但可测量地影响美白。
The phase-transition behavior of the NP-hard vertex-cover (VC) combinatorial optimization problem is studied numerically by linear programming (LP) on ensembles of random graphs. As the basic Simplex (SX) algorithm suitable for such LPs may produce incomplete solutions for sufficiently complex graphs, the application of cutting-plane (CP) methods is sought. We consider Gomory and {0,1/2} cuts. We measure the probability of obtaining complete solutions with these approaches as a function of the average node degree c and observe transition between typically complete and incomplete phase regions. While not generally complete solutions are obtained for graphs of arbitrarily high complexity, the CP approaches still advance the boundary in comparison to the pure SX algorithm, beyond the known replica-symmetry breaking (RSB) transition at c=e=2.718... . In fact, our results provide evidence for another algorithmic transition at c=2.90(2). Besides this, we quantify the transition between easy and hard solvability of the VC problem also in terms of numerical effort. Further we study the so-called whitening of the solution, which is a measure for the degree of freedom that single vertices experience with respect to degenerate solutions. Inspection of the quantities related to clusters of white vertices reveals that whitening is affected, only slightly but measurably, by the RSB transition.
