Placing items into compatible bucket types to find an optimal total value

Question

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?

Answer 1

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