编辑“︁近似算法”︁（章节）

=== 线性规划舍入 ===
线性规划舍入（LP Rounding）是另一种近似算法技术，通过求解松弛的线性规划问题并对解进行舍入得到整数解。

==== 示例：顶点覆盖问题 ====
'''问题描述'''：给定无向图 <math>G=(V,E)</math>，选择最小的顶点子集 <math>C \subseteq V</math>，使得每条边至少有一个端点在 <math>C</math> 中。

'''算法步骤'''：
1. 构造线性规划松弛问题。
2. 求解松弛问题得到分数解。
3. 对分数解进行舍入（如 <math>x_v \geq 0.5</math> 则选 <math>v</math>）。

'''近似比'''：2。