patternMinor
Placing items into compatible bucket types to find an optimal total value
Viewed 0 times
typestotalfindplacingoptimalintocompatiblevalueitemsbucket
Problem
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:
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?
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.821Is 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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#104854, answer score: 3
Revisions (0)
No revisions yet.