arXiv preprint ·
Faster Deterministic Approximation for Counting Knapsack
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Cascade: GPU-Accelerated Out-of-Core Suffix Array Construction for LLM Corpora
The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation
Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds
Random Fourier Features in Near-Linear Time
Optimal High Probability Bounds for Random Order Online Sorting
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.