# PTAS for a variant of multiple knapsack?

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

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

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.