Is this algorithm a c-approximation algorithm
In this problem, we will consider the following simple randomized algorithm for the Vertex Cover Algorithm.
Start with S = ∅
While S is not a vertex cover,
Select an edge e not covered by S
Select one end of e at random (each end equally likely)
Add the selected node to S
Endwhile
We will be interested in the expected cost of a vertex cover selected by this algorithm.
(a) Is this algorithm a c-approximation algorithm for the Minimum Weight Vertex Cover Problem for some constant c? Prove your answer.
(b) Is this algorithm a c-approximation algorithm for the Minimum Cardinality Vertex Cover Problem for some constant c? Prove your answer.
(Hint: For an edge, let pe denote the probability that edge e is selected as an uncovered edge in this algorithm. Can you express the expected value of the solution in terms of these probabilities? To bound the value of an optimal solution in terms of the pe probabilities, try to bound the sum of the probabilities for the edges incident to a given vertex v, namely
 
Answers
Status NEW
Posted 28 Apr 2017 04:04 PM
My Price 5.00
-----------
Attachments
file 1493397061-Answer.docx preview (299 words )
I-----------n t-----------his----------- pr-----------obl-----------em,----------- we----------- wi-----------ll -----------con-----------sid-----------er -----------the----------- fo-----------llo-----------win-----------g s-----------imp-----------le -----------ran-----------dom-----------ize-----------d a-----------lgo-----------rit-----------hm -----------for----------- th-----------e V-----------ert-----------ex -----------Cov-----------er -----------Alg-----------ori-----------thm-----------. -----------Sta-----------rt -----------wit-----------h S----------- = -----------∅----------- W-----------hil-----------e S----------- is----------- no-----------t a----------- ve-----------rte-----------x c-----------ove-----------r, ----------- Se-----------lec-----------t a-----------n e-----------dge----------- e -----------not----------- co-----------ver-----------ed -----------by -----------S -----------Sel-----------ect----------- on-----------e e-----------nd -----------of -----------e a-----------t r-----------and-----------om -----------(ea-----------ch -----------end----------- eq-----------ual-----------ly -----------lik-----------ely-----------) -----------Add----------- th-----------e s-----------ele-----------cte-----------d n-----------ode----------- to----------- S ----------- En-----------dwh-----------ile----------- W-----------e w-----------ill----------- be----------- in-----------ter-----------est-----------ed -----------in -----------the----------- ex-----------pec-----------ted----------- co-----------st -----------of -----------a v-----------ert-----------ex -----------cov-----------er -----------sel-----------ect-----------ed -----------by -----------thi-----------s a-----------lgo-----------rit-----------hm.----------- (-----------a) -----------Is -----------thi-----------s a-----------lgo-----------rit-----------hm -----------a c------------ap-----------pro-----------xim-----------ati-----------on -----------alg-----------ori-----------thm-----------
Not Rated(0)