6
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 8 '16 at 20:14
  • $\begingroup$ 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. $\endgroup$ – Ribz Mar 8 '16 at 21:25
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 8 '16 at 21:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ribz Mar 12 '16 at 17:00
  • $\begingroup$ @det No, it appears your estimate is too optimistic in general. Convergence can be much slower. $\endgroup$ – Yuval Filmus Mar 12 '16 at 17:01
  • $\begingroup$ Do you know of a way that let me derive the approximation ratio of BA? I mean what tools should I use? $\endgroup$ – Ribz Mar 12 '16 at 17:08
  • $\begingroup$ There's nothing general. You have to analyze your particular situation. $\endgroup$ – Yuval Filmus Mar 12 '16 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.