<p>I <em>think</em> there is no paper solving that exact problem, but "<a href="https://arxiv.org/abs/1007.1271" rel="nofollow">Online Vertex-Weighted Matching</a>" 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.</p>

<p>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.</p>

<p>(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.)</p>

CC BY-SA 3.0
2016-08-01T18:02:08.100Z
Thanks for you reference! Yes, this type of greedy relies on the knowledge of full weight order.
user2789928
CC BY-SA 3.0
2016-07-26T13:40:22.757Z
2016-07-29T13:09:10.300Z
2016-07-29T13:09:10.300Z
usul
<p>I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.</p>

<p>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&gt;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$.</p>

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

CC BY-SA 3.0
2016-07-22T10:49:29.260Z
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](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem)?  Have you researched the literature on that problem?  Is this a "network with gains" problem?
D.W.
CC BY-SA 3.0
2016-07-22T21:55:58.223Z
@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
CC BY-SA 3.0
2016-07-22T23:56:31.920Z
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/on-topic]: "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.
CC BY-SA 3.0
2016-07-30T15:06:20.290Z
Which side is the online side in your problem?
Yonatan N
CC BY-SA 3.0
2016-07-31T15:18:35.663Z
@YonatanN Nodes in left side arrive in online.
user2789928
<graph-theory><approximation-algorithms><matching><online-algorithms><bipartite-graphs>
Online/approximate weighted and capacitated bipartite matching
user2789928
# Online/approximate weighted and capacitated bipartite matching

(Asked by: username_0 on 2016-07-22)

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.

**Tags:** graph-theory, approximation-algorithms, matching, online-algorithms, bipartite-graphs
> **Comments:**
> **username_1**: 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](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem)?  Have you researched the literature on that problem?  Is this a "network with gains" problem?  
> **username_0**: @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?  
> **username_1**: 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/on-topic]: "Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing, not on shirking."  
> **username_2**: Which side is the online side in your problem?  
> **username_0**: @YonatanN Nodes in left side arrive in online.  

---

## 1 answers

### Answer by username_3 on 2016-07-26. Score: 2 | Accepted answer

I *think* there is no paper solving that exact problem, but "[Online Vertex-Weighted Matching](https://arxiv.org/abs/1007.1271)" 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.)

> **Comments:**
> **username_0**: Thanks for you reference! Yes, this type of greedy relies on the knowledge of full weight order.  

---

