Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914536232058880 |
|---|---|
| author | Chen, Lin Hu, Tingwei Mao, Yuchen Chen, Yong Mei, Lili Zhang, An Chen, Guangting Zhang, Guochuan |
| author_facet | Chen, Lin Hu, Tingwei Mao, Yuchen Chen, Yong Mei, Lili Zhang, An Chen, Guangting Zhang, Guochuan |
| contents | In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our goal is to assign items to knapsacks so as to maximize the minimum profit received by any knapsack subject to the capacity constraint.
When all knapsacks have identical capacity, we give a $(\frac{2}{3} - \varepsilon)$-approximation algorithm for any constant $\varepsilon > 0$. This result almost matches the $(\frac{2}{3} + \varepsilon)$ inapproximability bound for the bottleneck multiple subset sum problem (Caprara et al., 2000).
When the knapsacks can have arbitrary capacities, we propose a $(\frac{1}{2} - \varepsilon)$-approximation algorithm for any constant $\varepsilon > 0$. We also prove a hardness bound of $(\frac{1}{2} + \varepsilon)$ for any constant $\varepsilon > 0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05233 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems Chen, Lin Hu, Tingwei Mao, Yuchen Chen, Yong Mei, Lili Zhang, An Chen, Guangting Zhang, Guochuan Data Structures and Algorithms In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our goal is to assign items to knapsacks so as to maximize the minimum profit received by any knapsack subject to the capacity constraint. When all knapsacks have identical capacity, we give a $(\frac{2}{3} - \varepsilon)$-approximation algorithm for any constant $\varepsilon > 0$. This result almost matches the $(\frac{2}{3} + \varepsilon)$ inapproximability bound for the bottleneck multiple subset sum problem (Caprara et al., 2000). When the knapsacks can have arbitrary capacities, we propose a $(\frac{1}{2} - \varepsilon)$-approximation algorithm for any constant $\varepsilon > 0$. We also prove a hardness bound of $(\frac{1}{2} + \varepsilon)$ for any constant $\varepsilon > 0$. |
| title | Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.05233 |