# Online/approximate weighted and capacitated bipartite matching

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.

• 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? – D.W. Jul 22 '16 at 10:49
• @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? – user2789928 Jul 22 '16 at 21:55
• 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." – D.W. Jul 22 '16 at 23:56
• Which side is the online side in your problem? – Yonatan N Jul 30 '16 at 15:06
• @YonatanN Nodes in left side arrive in online. – user2789928 Jul 31 '16 at 15:18