5
$\begingroup$

I am interested in the following variant of multiple knapsack. There are $n$ items with values $v_1,\ldots,v_n$. We want to partition the items into $m$ subsets $S_1,\ldots,S_m$ to maximize $\min_{j\in\{1,\ldots,m\}}\sum_{i\in S_j} v_i$. In words, we want to assign the items to $m$ bins to maximize the minimum total value in any bin.

The problem is clearly NP-hard even for the case of two bins; it is essentially the PARTITION problem. However, SUBSET-SUM has an FPTAS and many generalizations of SUBSET-SUM and KNAPSACK have a PTAS; there are so many of them, though... Is there a generalization of these problems that is known to have a PTAS and captures my problem? (On the other hand, the problem is a special case of the Santa Claus problem [Bansal and Sviridenko, STOC'06], which seems to be quite hard to approximate.)

$\endgroup$
  • 2
    $\begingroup$ Welcome to cstheory! $\endgroup$ – Kaveh Oct 2 '13 at 18:53
  • 2
    $\begingroup$ Thank you! Based on this first, very positive, experience, it seems I'll be visiting this website frequently. $\endgroup$ – Ariel Procaccia Oct 3 '13 at 13:37
5
$\begingroup$

If I'm not mistaken, in the introduction of Bansal and Sviridenko, they mention that your special case - where children value items equally aka jobs take the same time on all machines - was the topic of Woeginger (1994) and shown to have a PTAS. Woeginger also points out that the problem is strongly NP-hard and hence does not permit an FPTAS unless P=NP.

Note however that if the number of bins $m$ is fixed rather than being part of the input, then the usual discretization method used for Knapsack and others, where items are rounded to powers of $(1+\epsilon/n)$, seems to yield an FPTAS.

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