Maurice Tutor

(5)

$15/per page/Negotiable

About Maurice Tutor

Levels Tought:
Elementary,Middle School,High School,College,University,PHD

Expertise:
Algebra,Applied Sciences See all
Algebra,Applied Sciences,Biology,Calculus,Chemistry,Economics,English,Essay writing,Geography,Geology,Health & Medical,Physics,Science Hide all
Teaching Since: May 2017
Last Sign in: 398 Weeks Ago, 2 Days Ago
Questions Answered: 66690
Tutorials Posted: 66688

Education

  • MCS,PHD
    Argosy University/ Phoniex University/
    Nov-2005 - Oct-2011

Experience

  • Professor
    Phoniex University
    Oct-2001 - Nov-2016

Category > Management Posted 06 Jan 2018 My Price 6.00

Vertex Cover 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

Maurice Tutor
(5)
Status NEW Posted 06 Jan 2018 09:01 PM My Price 6.00

Hel-----------lo -----------Sir-----------/Ma-----------dam-----------Tha-----------nk -----------You----------- fo-----------r u-----------sin-----------g o-----------ur -----------web-----------sit-----------e a-----------nd -----------acq-----------uis-----------iti-----------on -----------of -----------my -----------pos-----------ted----------- so-----------lut-----------ion-----------.Pl-----------eas-----------e p-----------ing----------- me----------- on-----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be-----------

Not Rated(0)