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

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

CC BY-SA 3.0
2013-10-03T02:22:54.637Z
2013-10-03T02:22:54.637Z
c.lorenz
<p>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.</p>

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

CC BY-SA 3.0
2013-10-02T18:53:21.560Z
Welcome to cstheory!
Kaveh
CC BY-SA 3.0
2013-10-03T13:37:00.193Z
Thank you! Based on this first, very positive, experience, it seems I'll be visiting this website frequently.
Ariel Procaccia
<approximation-algorithms>
PTAS for a variant of multiple knapsack?
Ariel Procaccia
# PTAS for a variant of multiple knapsack?

(Asked by: username_0 on 2013-10-02)

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

**Tags:** approximation-algorithms

> **Comments:**
> **username_1**: Welcome to cstheory!  
> **username_0**: Thank you! Based on this first, very positive, experience, it seems I'll be visiting this website frequently.  

---

## 1 answers

### Answer by username_2 on 2013-10-03. Score: 6 | Accepted answer

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.


---

