如何实现图顶点覆盖的整数线性规划公式的松弛？

Question

我正在实现来自顶点覆盖问题的核化算法:理论与实验(PDF)的优化算法。

我有点困在第2.3章:线性规划的核化。

这种技术的思想(在ILP公式中)是将权重X_u \in \left\{ 0,1 \right\}分配给输入图G=\left\( V,E \right\)的每个顶点u (也称为v)，以满足以下约束：

• 最小化权重\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，我需要如何接近松弛呢？

Answer 1

正如您已经注意到的，约束X_v in {0, 1/2, 1}不能作为(小数)线性规划来表示。这里要做的是，如果设置较弱的约束X_v >= 0，那么就存在一些最优解，其中X_v in {0, 1/2, 1}对所有v都有效，尽管通常不是每个最优解都具有这个性质。文章的第6节给出了一个算法，它为顶点覆盖LP找到了这样一个最优解。