1
$\begingroup$

Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a bucket type iff the item is able to be inserted into a bucket of that type. The goal is to insert the items into the buckets such that the total value of the inserted items is highest.

For example:

Items:
compatible with       | value
A,B,C                 | 17.641
A,B,C                 | 14.821
A,B                   | 14.274
A,B                   | 13.755
A,B                   | 12.240
A,B                   | 12.240
B,C                   | 11.960
A,B                   | 10.270
A,B,C                 | 9.958
A,B,C                 | 8.552

Buckets:
bucket type           | capacity
A                     | 2
B                     | 3
C                     | 4

Solution:
bucket                | values
A                     | 17.641, 12.240
B                     | 14.274, 13.755, 12.240
C                     | 11.960, 9.958, 8.552, 14.821

Is this problem a special case of any existing problems? I am finding it hard to envision an algorithm to solve it, but I feel that a good solution would require passing over the item list multiple times and maintaining a queue of best matches for each bucket type.

What would be the wost-case complexity of the resulting algorithm? Could a situation with 5 bucket types and 30 items explode in computational expense?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

You can formalize this problem as a minimum-cost flow problem.

You construct the graph as follows.

  • First construct a source vertex $s$ and a sink vertex $t$.

  • For each item $i$, add a vertex $u_i$ and add an edge from $s$ to $u_i$ with capacity 1 and with cost equal to the negation of the value of item $i$.

  • For each bucket $j$, add a vertex $v_j$ and add an edge from $v_j$ to $t$ with capacity equal to the capacity of bucket $j$ and with cost 0.

  • If item $i$ is compatible with bucket $j$, add an edge from $u_i$ to $v_j$ with capacity 1 and with cost 0.

Now you can use some polynomial time algorithm (for example, the cycle canceling algorithm) to find an integral solution of the minimum-cost flow problem. This integral solution then shows how you assign the items: if there is a flow 1 on $(u_i, v_j)$, then assign item $i$ to bucket $j$.

$\endgroup$
1
  • $\begingroup$ I was indeed able to solve this by using this method. There is a similar example of this being done in javascript here. The difference is that in this wedding example they are using a constant cost of zero for each edge, which in my case is replaced by the negation of the value of the item as per @xskxzr 's answer. $\endgroup$ Feb 26, 2019 at 22:49

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.

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