0
$\begingroup$

Consider a static offline bipartite graph where we have complete knowledge of the two sets of vertices $U$ and $V$. Now an edge is drawn between a vertex of $U$ and vertex of $V$ if the difference of the values associated with the respective vertices is minimum. The problem is to maximize the number of edges drawn. It is a one-to-one mapping. Once an edge is formed it cannot be reverted. Set $U$ and $V$ are not necessarily of equal size. There is no ordering on the elements in the set $U$ as they are considered in what so order they are at considered unit of time. A $U$ vertex value minus a $V$ vertex value should be greater than or equal to zero only to draw an edge. Can anyone explain and give the ratio of this mentioned matching algorithm performance to the optimum matching that can be found in this scenario?

$\endgroup$
  • $\begingroup$ Can you define "static" and "offline"? $\endgroup$ – Mike Pierce Jun 3 '15 at 4:36
  • $\begingroup$ Also, much of your post is hard to understand. In "...difference of the values associated with the respective vertices is minimum.", minimum among what? The sentence containing "... as they are considered in what so order they are at considered unit of time." is incoherent. What ratio are you looking for? $\endgroup$ – Mike Pierce Jun 3 '15 at 4:41
  • $\begingroup$ static refers that the values associated with the vertices in the U and V sets do not change and we know them. Offline refers that no new vertices are entering into the U and V sets. Actually both keywords meant to say that we have complete knowledge of the set U and set V before hand. $\endgroup$ – ksn Jun 3 '15 at 6:09
  • $\begingroup$ @Mike Pierce Say we have U set vertices with some values associated with each vertex. 'considered in what so order' I mean that there is no ordering like ascending or descending or any other criteria on those value. $\endgroup$ – ksn Jun 3 '15 at 6:18
  • $\begingroup$ Just pick a vertex 'u' from U and identify the minimum non negative difference of the value associated with it by looping over v's in the V set. Once identified, an edge is drawn between the corresponding 'u' and 'v'. Since it is one to one matching that 'v' wont be considered further. Continue with next 'u' from U set by repeating the same with rest out v's. $\endgroup$ – ksn Jun 3 '15 at 6:18
0
$\begingroup$

What you are describing sounds like a variation of the assignment problem, except that your version has that $|U|$ and $|V|$ are not necessarily equal. The Hungarian algorithm seems to be a good solution to the assignment problem, and I imagine that it can be modified pretty easily to fit your situation.

As for finding the performance ratio, the Hungarian algorithm works in $\operatorname{O}(n^3)$, so I would imagine that it would change to $\operatorname{O}(|U|^2|V|)$ after it is modified. You can compare this to the runtime of your approach which is $\operatorname{O}(|U||V|)$. If you wanted a hard numerical ratio, I would suggest coding up the modified Hungarian algorithm and your approach and collecting some data.

$\endgroup$
  • $\begingroup$ Can you explain the nature of the problem like it is np hard or under which category it falls. Can I refer the approach which I mentioned as greedy? $\endgroup$ – ksn Jun 3 '15 at 7:00
  • $\begingroup$ Can you please explain how it is |U|^2|V|) ? $\endgroup$ – ksn Jun 5 '15 at 5:21

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.