CAN WE IMPROVE K2+k To O(k)? BY LINEAR PROGRAMMING (LP)
Can we improve k 2 + k to O(k)? By linear programming (LP)
Vertex cover by LP For any graph G consider the linear program L(G) minimizesubject to xw+xw≥1 for all vwEE Xv+xw≥1 for all vwEE xw≥0 for allvEV xv≤1 for allvV Any integral solution of L(G)corresponds to a vertex cover of G
Vertex cover by LP For any graph G consider the linear program L(G) minimizeX v∈V xv subject to xv + xw > 1 for all vw ∈ E xv + xw > 1 for all vw ∈ E xv > 0 for all v ∈ V xv 6 1 for all v ∈ V Any integral solution of L(G) corresponds to a vertex cover of G
Half-intergral solutions Lemma (Nemhauser and Trotter,1975) Let G=(V,E)be a graph.Then L(G)has an optimal solution that is half-integral. Furthermore,a half-integral optimal solution of L(G)can be computed in polymomial time. A solution (x)vev is half-integral if xv∈0,1/2,1) for all vE V
Half-intergral solutions Lemma (Nemhauser and Trotter, 1975) Let G = (V, E) be a graph. Then L(G) has an optimal solution that is half-integral. Furthermore, a half-integral optimal solution of L(G) can be computed in polynomial time. A solution xv v∈V is half-integral if xv ∈ {0, 1/2, 1} for all v ∈ V
Proof(1) Let (be an optimal solution that is not half-integral.We will transform it into another optimal (such with fewer entries not in (0,1/2,1)than (vev We define :=min {xvlxy -1/21,lx-1x(0,1/2,1)} And for every vEV x+if0<x<1/2 x-E if0<xv<1/2 x-if 1/2<xv<1 andx= x+8 if1/2<xv<1 otherwise. otherwise
Proof (1) Let xv v∈V be an optimal solution that is not half-integral. We will transform it into another optimal x 0 v v∈V such with fewer entries not in {0, 1/2, 1} than xv v∈V . We define ε := min |xv|, |xv − 1/2|, |xv − 1| xv < {0, 1/2, 1} And for every v ∈ V x 0 v := xv + ε if 0 < xv < 1/2 xv − ε if 1/2 < xv < 1 xv otherwise. and x 00 v := xv − ε if 0 < xv < 1/2 xv + ε if 1/2 < xv < 1 xv otherwise