0
$\begingroup$

I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.

Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\in R$, it has capacity $c_i$ which means that at most $c_i$ nodes from $L$ can be matched to $r_i$. The objective function to maximize is $\sum_{i=1}^{n_2}x_iw_i$ where $x_i$ is the number of nodes in $L$ matched to $r_i$ and $w_i>0$ is the weight. The constraints are (1) $x_i\in\{0,...,c_i\}$, (2) any node in $L$ can be matched at most once and (3) any node $l_j$ is allowed to be matched to $r_i$ if $(l_j, r_i)$ $\in E$.

Is there any paper that solved the exact problem as I described above (provides either approximate or online algorithm)? To be clear, I am asking for references, and methods are not necessary.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ What approaches have you considered? How do you want to evaluate algorithms? (What's the most important metric? Running time on a sequential machine?) What's the best algorithm you've found so far? What's wrong with using linear programming? Isn't this just a minimum cost flow problem? Have you researched the literature on that problem? Is this a "network with gains" problem? $\endgroup$
    – D.W.
    Commented Jul 22, 2016 at 10:49
  • $\begingroup$ @D.W. Thanks for the comment. Yes, it can be solved as a mincost flow problem. After some literature research, I did not find a paper that either solves the (exact, not similar) problem in online setting or provides an approximate solution. Could you please point me out some closely related references? $\endgroup$
    – user2789928
    Commented Jul 22, 2016 at 21:55
  • 1
    $\begingroup$ Please edit your question to show us what papers/algorithms you've found and why they weren't suitable. Be specific about in what way they don't meet your requirements (e.g., if they don't solve your problem, explain in what way the problem they solve is different and which of your requirements they don't take into account). What's the best mincost flow algorithm you've found so far for your problem? See our help center: "Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing, not on shirking." $\endgroup$
    – D.W.
    Commented Jul 22, 2016 at 23:56
  • $\begingroup$ Which side is the online side in your problem? $\endgroup$
    – Yonatan N
    Commented Jul 30, 2016 at 15:06
  • $\begingroup$ @YonatanN Nodes in left side arrive in online. $\endgroup$
    – user2789928
    Commented Jul 31, 2016 at 15:18

1 Answer 1

Reset to default
2
$\begingroup$

I think there is no paper solving that exact problem, but "Online Vertex-Weighted Matching" by Aggarwal, Goel, Karande, and Mehta (2011) is very close. If I understood correctly, they solve your problem only with all capacities equal to one.

My best guess is that you will have to do some work to extend their guarantees and algorithm to your setting. On the other hand, a greedy algorithm probably should guarantee 0.5 of optimal by a standard argument: Consider the opt matching; for every "slot" in OPT left unmatched by greedy, there was some other match made that was more valuable (since the slot was available, its partner must have gone elsewhere). I hope you will forgive this discussion of methods contrary to your request.

(edit: I want to mention that this argument wouldn't work if the weights are on the arriving vertices; it's good to think about why.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for you reference! Yes, this type of greedy relies on the knowledge of full weight order. $\endgroup$
    – user2789928
    Commented Aug 1, 2016 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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