3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe you can try and maximize an entropy in some sense. But really you should not solve these problems too well before you get paid for it. $\endgroup$ – mathreadler Dec 2 '15 at 8:00
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I know greedy algorithm approach won't work, but I wasn't quite sure of any general algorithm that would work well here. $\endgroup$ – user98235 Dec 1 '15 at 2:23
  • $\begingroup$ The thing I was thinking of was following: in your example, just unlist all of them. 1, 1, 1, 2, 3, 20 then take the average: divide the sum by the number of boxes, then we'll get 28/2 = 14, then from there, we order those numbers, (1, 1, 1, 2, 3, 20), and then put numbers in one box until it exceeds 14, then if it exceeds, then we put the number, which made it exceed 14, into another box. $\endgroup$ – user98235 Dec 1 '15 at 2:25
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.