2
$\begingroup$

Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of the rocks in the buckets, while filling each bucket to its capacity.

An additional constraint is this: the rocks are themselves coloured red or blue, and can only be placed in a bucket of the corresponding colour. Moreover, the rocks can be coloured multiple different colours. In this case, the rock can be placed in any of the buckets with which it shares a colour.

For example, if our rocks are

$$\begin{array}{c|c|c|} & \text{Colours} & \text{Weight} \\ \hline \text{Rock 1} & \text{Red, blue} & 1\\ \hline \text{Rock 2} & \text{Red} & 2 \\ \hline \text{Rock 3} & \text{Red} & 3 \\ \hline \text{Rock 4} & \text{Blue} & 4 \\ \hline \text{Rock 5} & \text{Blue} & 5 \\ \hline \end{array}$$ then the optimal solution is $$\begin{array}{c|c} \text{Red Bucket} & \text{Blue Bucket} \\ \hline \text{Rock 2} & \text{Rock 1} \\ \text{Rock 3} & \text{Rock 4} \end{array}$$ as then the sum of the weights in the buckets is minimized.

One idea for an approximate algorithm as follows. First, sort the rocks in order of increasing weight. We make two passes of this list:

  • First pass: if the rock has only one colour, and if fewer than 2 rocks in the list so far have had that colour, then we can add that rock to the appropriate bucket. From the above example, we see that this step will place Rock 2 into the Red Bucket and Rock 4 into the Blue Bucket. (This step will never make an incorrect placement.)
  • Second pass (greedy): if the rock can fit into any of the buckets, put it there.

This algorithm does not generate the optimal solution for the above example, since on the second pass it will incorrectly place Rock 1 into the Red Bucket.

My question is this: does there exist a polynomial time algorithm to solve this problem optimally for $k$ buckets and $n$ rocks? If not, are there any polynomial time algorithms that generate approximate solutions (better than the one I've given here)?

$\endgroup$
  • $\begingroup$ So you can have $k$ buckets, but the capacity of each bucket is exactly 2 on all your instances? $\endgroup$ – md5 Oct 6 '19 at 23:57
  • $\begingroup$ @md5 that's correct $\endgroup$ – jacer21 Oct 7 '19 at 0:00
  • $\begingroup$ Just another question to make sure I understood the problem correctly. I can reduce the case with $k$ buckets to the problem: "you have $n$ elements and 2 buckets of capacity respectively $a$ and $b$, you're given for each element 2 bits (can go to bucket 1/can go to bucket 2) and you want to choose $a+b$ elements of minimal weight that can be partitioned into $a$ elements that can go to bucket 1 and $b$ that can go to bucket 2". Do you agree? $\endgroup$ – md5 Oct 7 '19 at 0:24
  • $\begingroup$ If that's true then I think there's an optimal greedy algorithm (greedily put the elements sorted by weight that can only go to bucket 1 (resp. 2) to bucket 1 (resp. 2) until you reach the capacity, and then if you look at the list of elements that you added, replace the elements in increasing order by elements that can go to both buckets sorted in decreasing order (I can write things a little bit more formally if needed) $\endgroup$ – md5 Oct 7 '19 at 0:30
  • 1
    $\begingroup$ @md5, how do you reduce the $k$ buckets case to the 2 buckets case? $\endgroup$ – Vincenzo Oct 7 '19 at 10:21
2
$\begingroup$

I assume that in the $k$ bucket case, each rock has up to $k$ colors (buckets) associated with it, which are the ones it can be put into.

It seems to me that a polynomial time algorithm can be obtained by reduction to a minimum-cost flow problem, which can be solved in polynomial time. Create a network with $k + n + 1$ nodes: $n$ rock nodes, $k$ bucket nodes, and $1$ source node. The source node is adjacent to each of the rock nodes, with edge capacity 1 and edge cost equal to the weight of the rock. Each rock node is also adjacent to all the bucket nodes it can be put into, with edge capacity 1 and edge cost 0. The source node has a supply of $2k$ units, and each bucket node has a demand of 2 units. Any integer flow of value $2k$ corresponds to a feasible assignment of $2k$ rocks to the buckets. The minimum cost integer flow corresponds to an assignment of minimum weight.

| cite | improve this answer | |
$\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.