# What is the approximation ratio of this randomized algorithm for finding matchings?

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: • I don't understand your problem. From your definition it looks like $\Pi_1$ depends only on $n$, which is kind of weird. I suspect you're not telling us everything. Therefore I suggest you describe $\Pi$ and $\Pi_1$ explicitly. Mar 8, 2016 at 20:14
• Thank you for your comment. Let me be more clear. On the one hand, $\Pi$ is the following problem: given a bipartite graph, select a maximum matching that respects some constraints C. On the other hand, $\Pi_1$ is the following problem: given two disjoint sets of nodes, create a maximum matching that respects constraints C. Hence, in an instance of $\Pi_1$, we do not know which edge to select. That's why in my algorithm I tried to create, randomly, some edges and then solve. I hope this is clear. If not, I will try to reformulate the whole question from the beginning when I get the chance.
– Ribz
Mar 8, 2016 at 21:25
• No, I still don't understand. Matching for me makes sense only for graphs. Perhaps you should spell out the constraints and give some examples. Mar 8, 2016 at 21:53

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.
• So, as $T$ goes large, BA produces a constant factor approximation solution. I cannot claim it is a $O(1+\frac{1}{T})$-approximation algorithm?