1
$\begingroup$

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with capacities $\overline B_{1}, \overline B_{2}, \dots, \overline B_{m}$, respectively. Considering that each ball is stored in exactly one bin, the problem is to find the maximum number of balls that can be stored in those $m$ bins under the following two constraints. First, for each ball $b_{ij}$ there is a set of bins $\hat B_{ij}$ such that $b_{ij}$ can only be stored in a bin in $\hat B_{ij}$. Second, balls forming a pair (e.g., $b_{21}$ and $b_{22}$) cannot be stored in the same bin.

My attempt consists of modelling this problem as a max-flow problem and then running the Ford–Fulkerson algorithm. I've built a graph $G$ with starting node $s$ and ending point $t$. The first layer of nodes are the $2n$ balls, and my second layer of nodes are the $m$ bins. The first layer and second layer are connected to match the first constraint and the capacity of those edges are all equal to one. All the nodes of the second layer are connected to the ending node $t$, and their capacities are $\overline B_{1}, \overline B_{2}, \dots, \overline B_{m}$. I don't know how to connect the starting node $s$ to the first layer of nodes and what the capacity of those edges should. It seems that it doesn't matter, but I'm not sure. Also, I don't know how to handle the second constraint.

$\endgroup$
1
$\begingroup$

You are on the right track.

Connect the starting node $s$ to each node in the first layer with an edge of capacity one.

Since the balls $b_{i1}$ and $b_{i2}$ cannot stored in the same bin, for each bin $X$ in $\hat B_{i1}\cap\hat B_{i2}$, instead of connecting $b_{i1}$ and $b_{i2}$ directly to the node $X$ in the second layer,

  • construct a node $c_{i,X}$ that connects to $X$ with capacity 1.
  • connect $b_{i1}$ to $c_{i,X}$ with an edge of capacity one.
  • connect $b_{i2}$ to $c_{i,X}$ with an edge of capacity one.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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