0

我正在实现顶点覆盖问题的内核化算法中的优化算法：理论和实验 (PDF)。

我有点卡在第 2.3 章：Kernelization by linear programming。

这种技术的想法（在 ILP 公式中）是为输入图的X_u \in \left\{ 0,1 \right\}每个顶点u（也表示为）分配一个权重，以满足以下约束：vG=\left\( V,E \right\)

  • 最小化权重总和\Sigma_uX_u
  • 满足X_u + X_v \geq 1只要\left\{ u,v \right \}被图中的一条边连接。

因此，作为输出，我得到一组顶点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？

4

1 回答 1

1

正如您所注意到的，约束X_v in {0, 1/2, 1}不适用于（分数）线性程序。这里发生的情况是，如果您设置较弱的约束X_v >= 0，则存在一些X_v in {0, 1/2, 1}适用于所有人的最优解v，尽管通常并非每个最优解都具有此属性。您链接的论文的第 6 节介绍了一种算法，该算法可以为顶点覆盖 LP 找到这样的最佳解决方案。

于 2014-07-20T17:32:14.043 回答