Consider an instance of Vertex Cover problem as shown in Figure $1.$ The cost of the five vertices

as follows: $c_1=2,c_2=5,c_3=4,c_4=4\mathrm{.}5,$ and $c_5=2,$ where $c_k$ denotes the cost of vertex $v_k$ for

$k=1,2,3,4,5.$

Fig. $1.$ The input graph for Question $1.$

$1\mathrm{.}1.$ Please compute the exact performance of Greedy and Pricing Algorithm $($PA$),$ where Greedy

works by adding vertices in a decreasing order of the cost until we get a vertex cover and breaking

ties following the order of $v_5,v_4,v_3,v_2,v_1,$ if any; and PA checks edges following the order of

$e_1,e_2,$dots,$e_7.$ You need to state clearly the final set of vertices output and the related cost for each

of the two algorithms. $(20$ Points$)$

$1\mathrm{.}2.$ Please present the linear program $($LP$)$ we should construct for the above instance. You need

to state clearly the three elements of the LP: variables, constraints, and objective. You do not need

to solve the LP$.(10$ Points$)$

$1\mathrm{.}3.$ Please present an example and related analysis showing that the approximation ratio of the

LP$-$based algorithm can be equal to $2.(5$ Points$)$