Metraipolis › archive › dc_d54932e8b490
Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D — arXiv:2608.27600
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.27600
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T11:52:22.506Z
- SHA-256 of the archived text
c1c51c131f6e5bc365a125d3ec85cf6eb75d3b68ed9907c3c485ecdb0e4d1b50- Stable URL of this page
https://metraipolis.com/documento/dc_d54932e8b490
How to cite
Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D — arXiv:2608.27600 — arXiv (en), https://arxiv.org/abs/2608.27600 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d54932e8b490 (Metraipolis archive dc_d54932e8b490, sha256 c1c51c131f6e5bc365a125d3ec85cf6eb75d3b68ed9907c3c485ecdb0e4d1b50)
BibTeX
@misc{dcd54932e8b490,
title = {Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D — arXiv:2608.27600},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.27600},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d54932e8b490; sha256 c1c51c131f6e5bc365a125d3ec85cf6eb75d3b68ed9907c3c485ecdb0e4d1b50},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27600. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We revisit the $d$-dimensional Vector Knapsack problem ($d$-Knapsack): Given a $d$-dimensional capacity vector and a set of items, each with a $d$-dimensional weight vector and a profit, the goal is to select a set of items that maximizes the total profit without exceeding the capacity in any dimension. For any $d\ge2$, the best known approximation scheme for $d$-Knapsack runs in time $O(n^{\lceil d/\varepsilon\rceil-d})$ [Caprara, Kellerer, Pferschy, Pisinger '00]. We improve this running time to $\widetilde O_{d,\varepsilon,\rho}(n^{\lceil\frac{d-1}{2\varepsilon}-\frac12+\rho\rceil}+n^d)$ for any $\varepsilon\in(0,1)$ and every parameter $\rho\in(0,1)$. We achieve this speedup by designing the first meet-in-the-middle algorithm for $d$-Knapsack. This requires replacing the LP solver used in prior algorithms by a highly efficient dynamic programming algorithm to generate representative solutions, building on an LP-based structural argument. This is the first improvement in over 25 years, and the first result that improves the exponent by a constant factor. We complement this by a fine-grained lower bound based on $k$-SUM showing that 2-Knapsack requires time $n^{\lceil\frac1{2\varepsilon}-\frac12 \rceil-o(1)}$. This establishes the optimal exponent of 2-Knapsack as $\frac1{2\varepsilon}\pm O(1)$, which is precise up to an additive $O(1)$. To the best of our knowledge, this is the first result that determines the optimal exponent more precisely than up to a factor $O(1)$, for any problem that admits a PTAS but no EPTAS. For the special case of 2-Knapsack we further attain a $(1-\varepsilon-\delta)$-approximation in time $\widetilde O_{\delta,\varepsilon}(n^{\lceil\frac1{2\varepsilon}-\frac12\rceil})$. This nearly matches our lower bound, as for a slightly better approximation ratio a slightly better running time is impossible -- so our algorithm is bicriteria-optimal.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.27600 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T11:23:11.248Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).