3
$\begingroup$

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.

enter image description here

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$.

enter image description here

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ It might be interesting to describe these trivial ways you're talking about. $\endgroup$
    – Auberon
    Mar 27, 2016 at 13:27
  • 1
    $\begingroup$ 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 $k$-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. $\endgroup$
    – D.W. ♦
    Mar 28, 2016 at 1:02
  • 1
    $\begingroup$ If the algorithm knows everything in advance except for the order of the points, it can "cheat" by precalculating the graph offline before it receives the first point, then read off its precalculated answer sheet for each point it receives. So are there parameters ($k$, maybe) that it doesn't know in advance? Also, are there any constraints on $f(v_k)$, or is it free to be as evil as possible? $\endgroup$
    – Jander
    Mar 29, 2016 at 17:50
  • $\begingroup$ Great questions! What I have not managed to mention properly, is that the sequence does not necessarily contain all points $k$ times, they might figure less times, but at most $k$ times. Regarding $f(v_k)$, I will add some comments in the question. $\endgroup$
    – utdiscant
    Mar 31, 2016 at 5:31

0

Reset to default

Your Answer

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