2026-08-18T03:18:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23428 2025-10-02T12:54:51Z ddc:004 open_access

Weakly Approximating Knapsack in Subquadratic Time Chen, Lin Lian, Jiayi Mao, Yuchen Zhang, Guochuan Knapsack FPTAS We consider the classic Knapsack problem. Let t and OPT be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least OPT/(1 + ε) and total weight at most t, then Knapsack can be solved in Õ(n + (1/(ε))²) time [Chen, Lian, Mao, and Zhang '24][Mao '24]. This running time is the best possible (up to a logarithmic factor), assuming that (min,+)-convolution cannot be solved in truly subquadratic time [Künnemann, Paturi, and Schneider '17][Cygan, Mucha, Węgrzycki, and Włodarczyk '19]. The same upper and lower bounds hold if one seeks a solution with total profit at least OPT and total weight at most (1 + ε)t. Therefore, it is natural to ask the following question. If one seeks a solution with total profit at least OPT/(1+ε) and total weight at most (1 + ε)t, can Knsapck be solved in Õ(n + (1/(ε))^{2-δ}) time for some constant δ > 0? We answer this open question affirmatively by proposing an Õ(n + (1/(ε))^{7/4})-time algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lin Chen and Jiayi Lian and Yuchen Mao and Guochuan Zhang 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.51 urn:nbn:de:0030-drops-234286 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.51 eng https://creativecommons.org/licenses/by/4.0/legalcode