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 applyLA
to this instance we could have selected, sayA = { {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 applyBA
to this instance we could get, sayformed edges in line 3 of BA = { {1, 2}, {2, 2}, {3, 4}, {4, 3} }
.Now we apply
LA
to this instance and we could obtainA = { {1, 2}, {4, 3} }
We continue until
t=T
, and then select the maximum cardinality setA
obtained, which isS
in line 7 ofBA
.
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: