Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to approximate the following NP-hard problem, which is similar to bin packing, but does not have a linear objective function:

minimize $\Sigma_{i=1, \ldots, W}$ max{$v_s$ | s $\in$ $S_i$}

s.t. $\Sigma_{s \in S_i} w_s \leq T$ $\forall i \in (1, \ldots, W)$.

where $v_s$ is the value (overhead) of item s, $w_s$ is the size of the item $s$, $T$ is the size of each bin, $S$ is the entire set of items, and {$S_1, \ldots, S_W$} partitions $S$.

For example, suppose that $w_1$ = $w_2$ = $w_3$ = 1, $T$ = 2, $v_1$ = $v_2$ = 2, and $v_3$ = 1. Then an optimal solution is {{1, 2}, {3}} where the objective function produces max{$v_1$,$v_2$}+max{$v_3$} = 2+1 = 3. A non-optimal solution is {{1}, {2,3}} where the objective function produces max{$v_1$} + max{$v_2$, $v_3$} = 2+2 = 4.

If I sort the items according to their decreasing values and start assigning items to bins in a greedy fashion (i.e., assign each item to the first bin that can accommodate the item), would I get say a 2-approximate result?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.