Efficient algorithm for optimization problem.

Question

I had an interesting interview problem today. Let's assume that we have n boxes, containing many numbers. For instance, let's say $n=4$, and four boxes contain the following numbers:

  first box - (3, 2, 5)            sum(first box) = 10
  second box - (1, 7, 4, 8)        sum(second box) = 20
  third box - (10, 5, 9)           sum(third box) = 24
  fourth box - (11)                sum(fourth box) = 11

Let's assume that we're given $'k'$, the number of times we could move a number from one box to another. What would be the best way to use that limited number of moves, so that

    $max( sum(box_i) )$

which in the above case would be

   max( sum(first box), sum(second box), sum(third box), sum(fourth box) ) 

is minimum?

For instance, in the above example, if $k=1,$ then the best move would be to move 5 or 9 to first or fourth box.

I was just using the greedy algorithm approach, but I was wondering if there are some well-known algorithms for this type of problem or similar type of problems.

Answer 1

This is not a full answer, but it's too long for a comment. The greedy method will not be good here. Imagine two boxes, the first containing $(1,1,1,20)$ and the second $(3,2)$. Now the greedy method will take the $20$ out of the first into the second and then back, but in fact, after $3$ moves, you can arrive at the optimal solution of $(20), (1,1,1,3,2)$.

I don't see how any version of the greedy method would be able to find this solution...

Answer 2

Sounds like some kind of discrete optimization problem. There are multiple ways of addressing such problems. For example:

• Constraint Programming (CP)
• Local Search
• Integer Programming (IP)

Some of them are derived from the Brute Force Algorithm, but they minimize the search space by pruning or inserting constraints on the search space. I'm quite new to this myself. I'm currently watching a great Coursera Tutorial which addresses these topics and algorithms. I think that can be a great resource for you to learn to solve such problems.

Source: https://class.coursera.org/optimization-003

Answer 3

This problem is NP-hard. You can reduce the 3-Partition Problem to your problem: Let an instance of 3-Partition be given by integers $a_1, \ldots, a_{3n}$. Create an instance of your problem with $n$ boxes where box $i$ initially contains integers $a_{3i}, a_{3i+1}, a_{3i+2}$. If you set $k = 3n$ then the objective value will be $$ \frac{1}{n} \sum_{i=1}^{3n}a_i $$ if and only if the 3-Partition Problem has a solution.

Since the 3-Partition Problem is strongly NP-hard I guess that you won't find a fast algorithm giving you the optimal solution.

For small values of $k$ is assume that searching through all possible combinations might be reasonable, though.