Efficient solution for a special assignment problem

Question

Given:

-A set of items that each have costs for being placed into a given container type.

-A set of container types that each have a number of available containers.

Example:

Amount*Container-Type : 5 * A, 3 * B, 2 * C

Items(Costs) :

3 * X (A=2, B=3, C=1)

2 * Y (A=5, B=2, C=2)

1 * Z (A=3, B=3, C=1)

Problem:

Find the best placement of the items into the containers so that the costs are minimal. For simplicity, only place an item into a single type of container.

I tried the hungarian method to solve the problem, but with a runtime of O(n³), it's quite prohibitive for large problems (e.g., 100000 items).

My current solution is a greedy approach, that just orders the item-container combinations by costs (asc) and assigns the first container with a sufficient amount left in O(n log n).

Is there a better solution?

Answer 1

Nahively I would go for a genetic aproach, given that genomes are easy to generate, mutate and cross-breed. but there may be an optimal non-combinatory solution.

Answer 2

If I understood your problem right, you only need some maths:

http://en.wikipedia.org/wiki/Optimization_%28mathematics%29

Answer 3

This problem is a variant of the Knapsack problem, start at the Wikipedia page and read on from there.

The greedy algorithm is known to be a reasonably good appoximation, so you are probably good enough.

Answer 4

Have you tried writing the assignment problem as a linear program and solving it using the simplex algorithm?

Answer 5

greed is good ;-)