2026-07-23T08:15:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25337 2026-03-19T13:03:42Z ddc:004 open_access

On the PTAS Complexity of Multidimensional Knapsack Doron-Arad, Ilan Kulik, Ariel Manurangsi, Pasin d-dimensional Knapsack Multidimensional Knapsack PTAS CSP We study the d-dimensional knapsack problem. We are given a set of items, each with a d-dimensional cost vector and a profit, along with a d-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A polynomial-time approximation scheme (PTAS) with running time n^{Θ(d/{ε})} has long been known for this problem, where {ε} is the error parameter and n is the encoding size. Despite decades of active research, the best running time of a PTAS has remained O(n^{⌈ d/{ε} ⌉ - d}). Unfortunately, existing lower bounds only cover the special case with two dimensions d = 2, and do not answer whether there is a n^{o(d/({ε)})}-time PTAS for larger values of d. In this work, we show that the running times of the best-known PTAS cannot be improved up to a polylogarithmic factor assuming the Exponential Time Hypothesis (ETH). Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions. Then, using a recent result of [Bafna Karthik and Minzer, STOC'25], we succeed in exhibiting tight trade-off between d and {ε} for all regimes of the parameters assuming d is sufficiently large. Informally, our result also shows that under ETH, for any function f there is no f(d/({ε)}) ⋅ n^{õ(d/({ε)})}-time (1-{ε})-approximation for d-dimensional knapsack, where n is the number of items and õ hides polylogarithmic factors in d/({ε)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilan Doron-Arad and Ariel Kulik and Pasin Manurangsi 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.50 urn:nbn:de:0030-drops-253377 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.50 eng https://creativecommons.org/licenses/by/4.0/legalcode