# prove: max (w(E), w(E)) is a 1/2 approximation to the value OPT

I don’t know the definition of $$1/2$$-approximation algorithm, but it looks like what you will need to do is the following argument:

For an enumeration $$sigma:Vto{1,2,…,n}$$ of the vertices, let, for each input graph $$G=(V,E)$$, the output of the algorithm be $$A_sigma(G)=max(w(overrightarrow{E}),w(overleftarrow{E}))$$.

We have that $$OPT(G)leq w(E)$$.

On the other hand,
begin{align} A_sigma(G)&=max(w(overrightarrow{E}),w(overleftarrow{E}))\ &geqfrac{w(overrightarrow{E})+w(overleftarrow{E})}{2}\ &= frac{w(E)}{2} end{align}
The last equation is because $$overrightarrow{E},overleftarrow{E}$$ is a partition of $$E$$.

Putting these two inequalities together we get $$OPT(G)leq w(E)leq 2A_sigma(G)$$

Therefore $$frac{A_sigma(G)}{OPT(G)}geq frac{1}{2}$$