<p>Input:</p>
<p><span class="math-container">$v_1,v_2,...,v_n$</span> item profits,</p>
<p><span class="math-container">$0&lt;w_1,w_2,...,w_n\leq1$</span> item weights.</p>
<p>Output: <span class="math-container">$B_1,B_2$</span> which are subsets of <span class="math-container">$\{1,2,...,n\}$</span> s.t. they are disjoint,
and such that
<span class="math-container">$\forall i\in\{1,2\}:\sum_{j\in B_i}w_j \leq1.$</span></p>
<p>Objective function: Maximize <span class="math-container">$\sum_{i=1}^2\sum_{j\in B_i}v_j$</span>.</p>
<p>Looking for an efficient PTAS. That is, for every <span class="math-container">$\epsilon&gt;0$</span> we should have an <span class="math-container">$(1-\epsilon)$</span> approximation using <span class="math-container">$f(\epsilon)n^{O(1)}$</span> where <span class="math-container">$f$</span> is any function.</p>
<p>TLDR: An EPTAS for multi-knapsack problem with fixed number of knapsack. I'd also prefer a solution based on rounding and dynamic programming.</p>
<p>The problem is that even if I knew what items are used for the solution, I'd still fail to find the actual solution...</p>
<p>I considered starting from one knapsack sized d. I found, online, EPTAS for the generalized Multiple knapsack problem, but I'd prefer a simpler solution to a simpler problem.</p>

CC BY-SA 4.0
2024-05-30T12:03:51.120Z
Have you tried looking at the EPTAS for general Multiple Knapsack and simplify it for your case?
Chandra Chekuri
CC BY-SA 4.0
2024-05-30T14:12:18.677Z
I did, but it still comes out complicated.
alon
<approximation-algorithms><combinatorics>
Efficient PTAS for 2 identical knapsacks?
alon
# Efficient PTAS for 2 identical knapsacks?

(Asked by: username_0 on 2024-05-30)

Input:

$v\_1,v\_2,...,v\_n$ item profits,

$0 item weights.

Output: $B\_1,B\_2$ which are subsets of $\{1,2,...,n\}$ s.t. they are disjoint,
and such that
$\forall i\in\{1,2\}:\sum\_{j\in B\_i}w\_j \leq1.$

Objective function: Maximize $\sum\_{i=1}^2\sum\_{j\in B\_i}v\_j$.

Looking for an efficient PTAS. That is, for every $\epsilon>0$ we should have an $(1-\epsilon)$ approximation using $f(\epsilon)n^{O(1)}$ where $f$ is any function.

TLDR: An EPTAS for multi-knapsack problem with fixed number of knapsack. I'd also prefer a solution based on rounding and dynamic programming.

The problem is that even if I knew what items are used for the solution, I'd still fail to find the actual solution...

I considered starting from one knapsack sized d. I found, online, EPTAS for the generalized Multiple knapsack problem, but I'd prefer a simpler solution to a simpler problem.

**Tags:** approximation-algorithms, combinatorics
> **Comments:**
> **username_1**: Have you tried looking at the EPTAS for general Multiple Knapsack and simplify it for your case?  
> **username_0**: I did, but it still comes out complicated.  

---

## 0 answers

