我正在实现来自 Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments (PDF) 的优化算法.
我有点卡在第 2.3 章:通过线性规划进行核化。
这种技术(在 ILP 公式中)的想法是为每个顶点 u 分配一个权重 X_u\in\left\{ 0,1\right\} (也表示为 v)输入图 G=\left\( V,E\right\) 以满足以下约束:
- 最小化权重之和
\Sigma_uX_u - 只要
\left\{ u,v\right\}通过图中的边连接，就满足X_u + X_v\geq 1。
因此，作为输出，我得到一组顶点的 X_v 为 1，其余的 X_v 为 0。
该论文称，松弛是基于将 X_u\in\left\{ 0,1\right\} 替换为 X_u\geq 0。 (S. Khuller (PDF) 指出在这种情况下 X_u\in\left\{ 0,0.5,1\right\})。这种松弛会导致 3 组顶点的权重分别为 1、0.5 和 0。
我的问题是我不太确定如何处理权重分配。
据我所知，为了最小化权重之和，最好(对于每条边)首先关注度数最高的顶点，当它们的权重已经大于零时，添加值到分析边的第二端的顶点。
这让我(正确地？)想到基本公式中每个顶点的实际 X_v\in\left\{ 0,1\right\} 的情况。当我考虑放宽整数约束时，它只是更改为 X_v\in\left\{ 0,0.5\right\}。
我的逻辑有什么缺陷？
我需要如何处理松弛以使顶点的权重为 1 和 0 以及 0.5？
最佳答案
如您所见，约束 X_v in {0, 1/2, 1} 不适用于(分数)线性规划。这里发生的事情是，如果您设置较弱的约束 X_v >= 0，则存在一些最佳解决方案，其中 X_v in {0, 1/2, 1}对所有 v 都成立，但通常不是每个最优解都具有此属性。您链接的论文的第 6 节介绍了一种算法，可以为顶点覆盖 LP 找到这样的最优解。
关于algorithm - 如何执行图顶点覆盖的整数线性规划公式的松弛？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24852038/