Greedy algorithm for stochastic matching is a 2-approximation

Details Greedy algorithm for stochastic matching is a 2-approximation Greedy algorithm for stochastic matching is a 2-approximation

2010-07-18

arxiv.org/abs/1007.3036v1

Computer Science

Data Structures and Algorithms

Scientific paper

The stochastic matching problem was first introduced by Chen, Immorlica, Karlin, Mahdian, and Rudra (ICALP 2009). They presented greedy algorithm together with an analysis showing that this is a 4-approximation. They also presented modification of this problem called multiple-rounds matching, and gave O(log n)-approximation algorithm. Many questions were remaining after this work: is the greedy algorithm a 2-approximation, is there a constant-ratio algorithm for multiple-rounds matching, and what about weighted graphs? For the last two problems constant-factor approximations were given in the work of Bansal, Gupta, Nagarajan, and Rudra, and in the work of Li and Mestre. In this paper we are answering to the first question by showing that the greedy algorithm is in fact a 2-approximation.

Affiliated with

Also associated with

No associations

Rating

Greedy algorithm for stochastic matching is a 2-approximation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Greedy algorithm for stochastic matching is a 2-approximation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Greedy algorithm for stochastic matching is a 2-approximation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-61625