[Solved]: What is the approximation ratio of this randomized algorithm for finding matchings?

Problem Detail: 

I would like to analyze the following algorithm in terms of its approximation ratio.

Here is the algorithm:

Input: A positive number T and two disjoint sets of nodes V={v1,...,vn} and W={w1,...,wn}. Output: A matching S. 1: O = [] # An empty array. 2: for t = 1 to T do 3:     Create a set E of edges from V to W randomly 4:     A = LA(G) # G is the bipartite graph G=(V U W, E) and LA is                  # an algorithm that takes as input a bipartite graph                  # and outputs a matching A. 5:     O[t] = A # Put the matching A in the t-th element of O. 6: end for 7: S = max(O) # S is the maximum cardinality matching in O. 8: return S 

In the algorithm above, called BA, there is a call to another algorithm LA, on line 4. We know that LA is a constant factor approximation algorithm for an NP-hard problem $\Pi$. An instance of $\Pi$ is a bipartite graph and we would like to return a maximum matching that respects some constraints. Therefore, LA will return a matching of size no less than a constant factor times the size of the optimal matching.

Note that BA is trying to solve another NP-hard problem $\Pi_1$ that has an instance of two sets and we would like to return a maximum matching between these two sets that respects the same constraints as for $\Pi$. The only difference between $\Pi$ and $\Pi_1$ is that $\Pi$ has as input a bipartite graph (nodes and edges) whereas $\Pi_1$ has as input a set of nodes only.

I am not trying to hide the constraints. I still cannot write them explicitly in a readable way. I will give some examples to clarify the problem.

• Say, for problem $\Pi$, we are given the following graph (it is represented by set of edges):

  Instance of II = { {1, 3}, {2, 2}, {3, 1}, {4, 4} }

  In this special instance, say, the optimal solution is

  OPT of II = { {1, 3}, {2, 2}, {4, 4} }

  Hence edge {3, 1} cannot exist in the solution because of the constraints. If we apply LA to this instance we could have selected, say

  A = { {1, 3}, {2, 2} }

  Therefore, the algorithm failed to select the edge {4, 4}.

• Now, for problem $\Pi_1$, we are given the following two sets:

  Instance of II1 = (V = { 1, 2, 3, 4 } and W = { 1, 2, 3, 4 })

  In this special instance, say, the optimal solution is (brute-force on all possible edges between V and W and apply the optimal algorithm for $\Pi$)

  OPT of II1 = { {1, 4}, {2, 3}, {3, 1}, {4, 2} }

  Hence, since we do not have the set of edges initially, the optimal solution for $\Pi_1$ is to select 4 edges unlike 3 edges for $\Pi$. In fact, it is clear that |OPT of II| <= |OPT of II1|.

  Now, at iteration t=1, if we apply BA to this instance we could get, say

  formed edges in line 3 of BA = { {1, 2}, {2, 2}, {3, 4}, {4, 3} }.

  Now we apply LA to this instance and we could obtain A = { {1, 2}, {4, 3} }

  We continue until t=T, and then select the maximum cardinality set A obtained, which is S in line 7 of BA.

Knowing that LA is $O(1)$-approximation algorithm for $\Pi$, can I say that BA is an approximation algorithm for $\Pi_1$?

I think I can say that BA is something like $O(1+\frac{1}{T})$-approximation algorithm for $\Pi_1$ because as $T\to\infty$ and the 3rd line of BA is generated uniformly random, the solution produced by BA is no less than a constant factor times the optimal solution.

The pseudo-code is also given in more clearer way here:

Asked By : Riebuoz

Answered By : Yuval Filmus

Suppose that the only feasible solution are single edges and $\{(1,1),(2,2),\ldots,(n,n)\}$. The optimal solution thus has value $n$. On the other hand, the optimal solution on a random bipartite graph is $1$ with probability $1-2^{-n}$. Thus algorithm BA would have to take $T=\Omega(2^n)$ in order to guarantee a constant approximation ratio, even though algorithm LA always outputs the optimal solution.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54121

3.2K people like this

 Download Related Notes/Documents