线性规划松驰化 最大二分图匹配： max∑eeECeXe ∑ee6o)xe≤1 v∈V ·xe∈{0,1 He∈E 但是，松驰化对于很多多项式时间可解的组合优化问题，往往可 以证明松驰化，之后并没有误差 分数解也可以转化为整数解 LP因此被广泛认为是一个解决组合优化问题的“统一算法框架” 直观的解释：这些LP的polytope的顶点都在整数点上 17 线性规划松驰化 最大二分图匹配： • max ∑*∈, �*�* • ∑*∈- . �* ≤ 1 • �* ∈ {0,1} 但是，松驰化对于很多多项式时间可解的组合优化问题，往往可 以证明松驰化之后并没有误差 分数解也可以转化为整数解 LP因此被广泛认为是一个解决组合优化问题的“统一算法框架” 直观的解释：这些LP的polytope的顶点都在整数点上 17 ∀� ∈ � ∀� ∈ �