线性规划松驰化 最大独立集： max∑vEVCvXv xu+Xv≤1 Vuv∈E ·xv∈{0,1 松驰化(relaxation):xv∈{0,1}松驰化为xv∈[0,1]。先找出一个分数解，然 后再从分数解里面想办法找出一个整数解 最坏的情况下面，松驰化可能引入非常大的误差。 考虑完全图上的最大独立集，最优的分数解和整数解之间相差多少？ 16线性规划松驰化 最大独立集： • max ∑T∈U �T�T • �! + �T ≤ 1 • �T ∈ {0,1} 松驰化 (relaxation)：�% ∈ {0,1} 松驰化为 �T ∈ [0,1]。先找出一个分数解，然 后再从分数解里面想办法找出一个整数解 最坏的情况下面，松驰化可能引入非常大的误差。 考虑完全图上的最大独立集，最优的分数解和整数解之间相差多少？ 16 ∀�� ∈ �