2026-07-20T11:57:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9068 2024-03-06T10:43:17Z ddc:004 open_access

A Faster FPTAS for #Knapsack Gawrychowski, Pawel Markin, Liran Weimann, Oren knapsack approximate counting K-approximating sets and functions Given a set W = {w_1,..., w_n} of non-negative integer weights and an integer C, the #Knapsack problem asks to count the number of distinct subsets of W whose total weight is at most C. In the more general integer version of the problem, the subsets are multisets. That is, we are also given a set {u_1,..., u_n} and we are allowed to take up to u_i items of weight w_i. We present a deterministic FPTAS for #Knapsack running in O(n^{2.5}epsilon^{-1.5}log(n epsilon^{-1})log (n epsilon)) time. The previous best deterministic algorithm [FOCS 2011] runs in O(n^3 epsilon^{-1} log(n epsilon^{-1})) time (see also [ESA 2014] for a logarithmic factor improvement). The previous best randomized algorithm [STOC 2003] runs in O(n^{2.5} sqrt{log (n epsilon^{-1})} + epsilon^{-2} n^2) time. Therefore, for the case of constant epsilon, we close the gap between the O~(n^{2.5}) randomized algorithm and the O~(n^3) deterministic algorithm. For the integer version with U = max_i {u_i}, we present a deterministic FPTAS running in O(n^{2.5}epsilon^{-1.5}log(n epsilon^{-1} log U)log (n epsilon) log^2 U) time. The previous best deterministic algorithm [TCS 2016] runs in O(n^3 epsilon^{-1}log(n epsilon^{-1} log U) log^2 U) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Gawrychowski and Liran Markin and Oren Weimann 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.64 urn:nbn:de:0030-drops-90687 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.64 eng https://creativecommons.org/licenses/by/3.0/legalcode