Primal-Dual Primal: min 7x1 +x2+ 5c3 S.t. T1 X2 + 3c3 10 5c1 2c2 X3 ≥ 6 x1,x2,x3≥0 Dual: max 10y1+6y2 vdual feasible ≤primal OPT S.t. 41 + 5y2 ≤ 7 -y1 + 2y2 1 3y1 y2 5 LP∈NP∩coNP y1,y2 ≥0Primal-Dual min 7x1 + x2 + 5x3 s.t. x1, x2, x3 ￾ 0 10y1 + 6y2 y1 + 5y2 ⇥ 7 ￾y1 + 2y2 ⇥ 1 3y1 ￾ y2 ⇥ 5 y1, y2 ￾ 0 x1 ￾ x2 + 3x3 ⇥ 10 5x1 + 2x2 ￾ x3 ⇥ 6 max s.t. Primal: Dual: ∀dual feasible ≤ primal OPT LP ∈ NP∩coNP