Approximately Counting Knapsack Solutions in Subquadratic Time
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912093637181440 |
|---|---|
| author | Feng, Weiming Jin, Ce |
| author_facet | Feng, Weiming Jin, Ce |
| contents | We revisit the classic #Knapsack problem, which asks to count the Boolean points $(x_1,\dots,x_n)\in\{0,1\}^n$ in a given half-space $\sum_{i=1}^nW_ix_i\le T$. This #P-complete problem admits $(1\pmε)$-approximation. Before this work, [Dyer, STOC 2003]'s $\tilde{O}(n^{2.5}+n^2{ε^{-2}})$-time randomized approximation scheme remains the fastest known in the natural regime of $ε\ge 1/polylog(n)$. In this paper, we give a randomized $(1\pmε)$-approximation algorithm in $\tilde{O}(n^{1.5}{ε^{-2}})$ time (in the standard word-RAM model), achieving the first sub-quadratic dependence on $n$. Such sub-quadratic running time is rare in the approximate counting literature in general, as a large class of algorithms naturally faces a quadratic-time barrier.
Our algorithm follows Dyer's framework, which reduces #Knapsack to the task of sampling (and approximately counting) solutions in a randomly rounded instance with poly(n)-bounded integer weights. We refine Dyer's framework using the following ideas:
- We decrease the sample complexity of Dyer's Monte Carlo method, by proving some structural lemmas for typical points near the input hyperplane via hitting-set arguments, and appropriately setting the rounding scale.
- Instead of running a vanilla dynamic program on the rounded instance, we employ techniques from the growing field of pseudopolynomial-time Subset Sum algorithms, such as FFT, divide-and-conquer, and balls-into-bins hashing of [Bringmann, SODA 2017].
We also need other ingredients, including a surprising application of the recent Bounded Monotone (max,+)-Convolution algorithm by [Chi-Duan-Xie-Zhang, STOC 2022] (adapted by [Bringmann-Dürr-Polak, ESA 2024]), the notion of sum-approximation from [Gawrychowski-Markin-Weimann, ICALP 2018]'s #Knapsack approximation scheme, and a two-phase extension of Dyer's framework for handling tiny weights. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22267 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximately Counting Knapsack Solutions in Subquadratic Time Feng, Weiming Jin, Ce Data Structures and Algorithms We revisit the classic #Knapsack problem, which asks to count the Boolean points $(x_1,\dots,x_n)\in\{0,1\}^n$ in a given half-space $\sum_{i=1}^nW_ix_i\le T$. This #P-complete problem admits $(1\pmε)$-approximation. Before this work, [Dyer, STOC 2003]'s $\tilde{O}(n^{2.5}+n^2{ε^{-2}})$-time randomized approximation scheme remains the fastest known in the natural regime of $ε\ge 1/polylog(n)$. In this paper, we give a randomized $(1\pmε)$-approximation algorithm in $\tilde{O}(n^{1.5}{ε^{-2}})$ time (in the standard word-RAM model), achieving the first sub-quadratic dependence on $n$. Such sub-quadratic running time is rare in the approximate counting literature in general, as a large class of algorithms naturally faces a quadratic-time barrier. Our algorithm follows Dyer's framework, which reduces #Knapsack to the task of sampling (and approximately counting) solutions in a randomly rounded instance with poly(n)-bounded integer weights. We refine Dyer's framework using the following ideas: - We decrease the sample complexity of Dyer's Monte Carlo method, by proving some structural lemmas for typical points near the input hyperplane via hitting-set arguments, and appropriately setting the rounding scale. - Instead of running a vanilla dynamic program on the rounded instance, we employ techniques from the growing field of pseudopolynomial-time Subset Sum algorithms, such as FFT, divide-and-conquer, and balls-into-bins hashing of [Bringmann, SODA 2017]. We also need other ingredients, including a surprising application of the recent Bounded Monotone (max,+)-Convolution algorithm by [Chi-Duan-Xie-Zhang, STOC 2022] (adapted by [Bringmann-Dürr-Polak, ESA 2024]), the notion of sum-approximation from [Gawrychowski-Markin-Weimann, ICALP 2018]'s #Knapsack approximation scheme, and a two-phase extension of Dyer's framework for handling tiny weights. |
| title | Approximately Counting Knapsack Solutions in Subquadratic Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.22267 |