Deterministic algorithm speeds up approximate counting in knapsack problem
Faster Deterministic Approximation for Counting Knapsack
Data Structures and Algorithms
Summary
The paper studies the problem of counting how many groups of items can fit into a knapsack without exceeding its weight limit. This is a hard problem to solve exactly, so researchers often look for fast ways to get very close answers. Previous work used random methods or slower deterministic ones, but the authors found a deterministic way to speed up the approximation. Their new method simulates a technique that was thought to only work with randomness, allowing faster and guaranteed approximate counting.
What this means in practice
- •For algorithm engineers: Create faster and reliable approximate counting tools for resource allocation problems where exact counts are infeasible.
- •For operations research teams: Improve solution speed when estimating feasible option counts in complex scheduling or packing scenarios using guaranteed approximations.
A theory result. No direct application yet.
Authors
Ce Jin, Jaewoo Park, Barna Saha
Abstract
Given $n$ nonnegative integer weights $w_1, \ldots, w_n$ and an integer knapsack capacity $T$, the $\#$Knapsack problem asks to count the number of subsets $I \subseteq \{1, 2, \dots, n\}$ such that $\sum_{i \in I} w_i \le T$. A long line of research has been devoted to designing faster $(1 \pm \varepsilon)$-approximation algorithms for this \#P-hard problem. Until very recently, the best-known time complexity was $\tilde{O}\bigl(n^{2.5}/\mathrm{poly}(\varepsilon)\bigr)$, achieved by the randomized algorithm of [Dyer, STOC 2003] and the deterministic algorithm of [Gawrychowski, Markin, and Weimann, ICALP 2018]. The recent work by [Feng and Jin, SODA 2025] improved the randomized complexity to $\tilde{O}\bigl(n^{1.5}/\mathrm{poly}(\varepsilon)\bigr)$, leaving open the question whether this $n^{2.5}$ barrier could also be broken by a \emph{deterministic} algorithm. In this work, we answer this question in the affirmative by presenting a deterministic $(1 + \varepsilon)$-approximation algorithm for \#Knapsack in $\tilde{O}\bigl(n^{2.4}/\mathrm{poly}(\varepsilon)\bigr)$ time. Our key technical innovation is to deterministically simulate the balancing technique, which was previously used in the literature of knapsack-type problems via random partitions and seemed to require randomization.