Utility Maximizing Assignment

Question

I posted this on computer science section but no one replied :(. Any help would be greatly appreciated :).

There is a grid of size MxN. M~20000 and N~10. So M is very huge. So one way is to look at this is N grid blocks of size M placed side by side. Next assume that there are K number of users who each have a utility matrix of MxN, where each element provides the utility that the user will obtain if that user is assigned that grid element. The allocation needs to be done in a way such for each assigned user total utility must exceed a certain threshold utility U in every grid block. Assume only one user can be assigned one grid element. What is the maximum number of users that can be assigned?. (So its okay if some users are not assigned ).

Level 2: Now assume for each user at least n out N blocks must exceed utility threshold U. For this problem, whats the maximum number of users that can be assigned.

Of course brute force search is of no use here due to K^(MN) complexity. I am guessing that some kind of dynamic programming approach maybe possible.

Answer 1

Using a different interpretation of your question than Codor, I am going to claim that (at least in theory, in the worst case) it is a hard problem.

Suppose that we can solve it in the special case when there is one block which must be shared between two users, who each have the same utility for each cell, and the threshold utility U is (half of the total utility for all the cells in the block), minus one.

This means that in order to solve the problem we must take a list of numbers and divide them up into two sets such that the sum of the numbers in each set is the same, and is exactly half of the total sum of the numbers available.

This is http://en.wikipedia.org/wiki/Partition_problem, which is NP complete, so if you could solve your problem as I have described it you could solve a problem known to be hard.

(However the Wikipedia entry does say that this is known as "the easiest hard problem" so even if I have described it correctly, there may be solutions that work well in practice).

Answer 2

To my understanding, the problem can be modelled as a Maximum Bipartite Matching problem, which can be solved efficiently with the Hungarian algorithm. In the left partition L, create K nodes, one for each user. In the right partition R, create L*M*N nodes, one for each cell in the grid. As edges create edges for each l in L and r in R with cost equal to the cost of the assignment of user l to the grid cell r.