2026-07-24T05:06:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10652 2024-03-06T10:46:23Z ddc:004 open_access

An Improved FPTAS for 0-1 Knapsack Jin, Ce approximation algorithms knapsack subset sum The 0-1 knapsack problem is an important NP-hard problem that admits fully polynomial-time approximation schemes (FPTASs). Previously the fastest FPTAS by Chan (2018) with approximation factor 1+epsilon runs in O~(n + (1/epsilon)^{12/5}) time, where O~ hides polylogarithmic factors. In this paper we present an improved algorithm in O~(n+(1/epsilon)^{9/4}) time, with only a (1/epsilon)^{1/4} gap from the quadratic conditional lower bound based on (min,+)-convolution. Our improvement comes from a multi-level extension of Chan’s number-theoretic construction, and a greedy lemma that reduces unnecessary computation spent on cheap items. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ce Jin 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.76 urn:nbn:de:0030-drops-106527 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.76 eng https://creativecommons.org/licenses/by/3.0/legalcode