I have $N$ nodes $v_1,\ldots,v_N$ in one partition $X$ and $M \leq N$ nodes $u_1,\ldots,u_M$ in a different partition $Y$. I want to connect nodes in $X$ to nodes in $Y$ with edges under the following constraints:Each node in $X$ must be connected to at most $k$ nodes in $Y$For each node $v_t$ there is a node $u_{f(v_t)}$ that it can not be connected to.I want to do it in an online fashion: I will get a stream of nodes from $X$ and then immediately connect that node to a node in $Y$. This edge can not be removed.After processing each node in the stream, then the difference between the maximum degree of nodes in $Y$ and the minimum degree of nodes in $Y$ should be as small as possible.In a simple case of the problem, assume that $N = M$ and that $f(v_t)=t$.Doing this in trivial ways lead to situations where I can end up with a difference of 2 in degrees for small examples.Edits to address comments:Comment: I don't understand what the inputs are and in what order they are presented. What does it mean to get a node? What information is provided along with that node? Also, what do you mean by After ..., the difference should be as small as possible? Does this mean that there are two phases: the first phase is to find edges that provide at least kk-connectivity; the second phase is to add more edges to minimize the difference in degrees? If so, this seems like it should be split into two separate questions, as those phases seem independent.By getting a node, it means you are given an index $i$ of referring to the node $v_i$ in $X$. After refers to when the stream of nodes ends. It was not clear in my original question that in this stream of nodes, each node $v_i$ will appear exactly $k$ times. For $N=3$ and $k=2$, this might look like $v_1,v_3,v_1,v_2,v_2,v_3$.Comment: It might be interesting to describe these trivial ways you're talking about.Sure. Say that our algorithm for selecting which node in $Y$ to connect a node (in $X$) to is the following: Take the node in $Y$ which has the lowest degree. If there is a tie, take the one with the lowest index ($u_1$ before $u_2$ for example).Let $N=3$, $M=3$ and $k=1$ and the stream of nodes/indices be $v_1,v_2,v_3$. Let $f(v_t)=t$. For the first node $v_1$, we connect it to $u_2$ (since $v_1$ can't be connected to $u_{f(v_1)} = u_1$, all edges have degree 0 and since we tie-break by lowest index). Next $v_2$ gets connected to $u_1$ (since it can't be connected to $u_2$ and since $u_1$ and $u_3$ have degree 0 and $u_1$ has the lowest index). Finally $v_3$ gets connected to $u_1$ since it can't be connected to $u_3$, and since $u_1$ and $u_2$ both have degree 1.In this case, we end up with $\text{degree}(u_1)=2$, $\text{degree}(u_2)=1$ and $\text{degree}(u_3)=0$. A better strategy would have been to connect $v_1$ to $u_2$, $v_2$ to $u_3$ and $v_3$ to $u_1$.
Online bipartite edge-cover problem with requirements
graph theory;bipartite matching;online algorithms