<p>I would like to solve a multi-dimensional 0-1 Knapsack problem, by looking for approximation algorithms with constant approximation ratio if possible. Here the particularity is that the number of dimensions <span class="math-container">$m$</span> may be as high as the input size. Hence existing approximation algorithms cannot be applied. How can I approach this problem?</p>

CC BY-SA 4.0
2022-04-19T15:17:08.013Z
Multi-dimensional Knapsack with high number of dimensions are also called Packing Integer Programs (PIPs) and they capture Maximum Independent Set in graphs as a special case so it is very hard to approximate. Here is an old paper of mine on this topic - hardness results have been improved since then but you can look them up. http://chekuri.cs.illinois.edu/papers/vector-sicomp.pdf
Chandra Chekuri
CC BY-SA 4.0
2022-04-20T02:01:34.093Z
Thank you for your comment and suggestion. I will look into them.
lchen
<ds.algorithms><co.combinatorics><approximation-algorithms>
Multi-dimensional 0-1 Knapsack problem with a high number of dimensions
lchen
# Multi-dimensional 0-1 Knapsack problem with a high number of dimensions

(Asked by: username_0 on 2022-04-19)

I would like to solve a multi-dimensional 0-1 Knapsack problem, by looking for approximation algorithms with constant approximation ratio if possible. Here the particularity is that the number of dimensions $m$ may be as high as the input size. Hence existing approximation algorithms cannot be applied. How can I approach this problem?

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms
> **Comments:**
> **username_1**: Multi-dimensional Knapsack with high number of dimensions are also called Packing Integer Programs (PIPs) and they capture Maximum Independent Set in graphs as a special case so it is very hard to approximate. Here is an old paper of mine on this topic - hardness results have been improved since then but you can look them up. http://chekuri.cs.illinois.edu/papers/vector-sicomp.pdf  
> **username_0**: Thank you for your comment and suggestion. I will look into them.  

---

## 0 answers

