Open codershenghai opened 5 years ago
http://www.zhangshenghai.com/posts/20007/
使用线性规划来近似顶点覆盖问题ILP（整数线性规划）对于每一个顶点$v\in V$，有$x(v) \in {0, 1}$，$x(v)=1$意为v在顶点覆盖中，$x(v)=0$意为v不再顶点覆盖中。那么，对于顶点覆盖问题的任意边$(u, v)$，u和v至少有一个必须在顶点覆盖中，即$x(u)+x(v)\geq1$。这样就引出了以下用于寻找最小顶点覆盖的0-1整数规划 。 min \sum_{v
http://www.zhangshenghai.com/posts/20007/
使用线性规划来近似顶点覆盖问题ILP（整数线性规划）对于每一个顶点$v\in V$，有$x(v) \in {0, 1}$，$x(v)=1$意为v在顶点覆盖中，$x(v)=0$意为v不再顶点覆盖中。那么，对于顶点覆盖问题的任意边$(u, v)$，u和v至少有一个必须在顶点覆盖中，即$x(u)+x(v)\geq1$。这样就引出了以下用于寻找最小顶点覆盖的0-1整数规划 。 min \sum_{v