CHAPTER10 线性规划在近似算法中的应用

发布网友发布时间：2023-07-24 00:41

共1个回答

热心网友时间：2024-10-23 17:47

本文来自我的个人博客 https://www.zhangshenghai.com/posts/20007/

对于每一个顶点，有，意为v在顶点覆盖中，意为v不再顶点覆盖中。那么，对于顶点覆盖问题的任意边，u和v至少有一个必须在顶点覆盖中，即。这样就引出了以下用于寻找最小顶点覆盖的0-1整数规划。

假设去掉了这一*，并代之以，就可以得到以下的线性规划，称为线性规划松弛。

对于每一个顶点v，都会求得一个的值，对做以下的rounding：

若，则将该顶点加入到点覆盖集合中（），否则舍去顶点v（），直至图中的所有顶点处理完毕。

由以上算法可看出：

故此算法是一个近似度为2的近似算法。