Deterministic Volume Estimation of Truncated Hypercubes
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914580455751680 |
|---|---|
| author | Gunluk, Kyra |
| author_facet | Gunluk, Kyra |
| contents | We present a deterministic polynomial-time algorithm for estimating the volume of a hypercube intersected by a fixed number of constraints of the type $f(x) \leq b$, where $f$ is the sum of univariate functions that are each nonnegative, monotone, and convex. Such constraints include knapsack and norm-ball constraints. The case of the unit hypercube truncated by a single linear constraint (halfspace) is already #P-hard. Given $k$ such constraints in dimension $n$, with total input length of at most $L$ bits, total output length of at most $L_o$ bits, and an error parameter $\varepsilon > 0$, our algorithm computes a $(1 + \varepsilon)$-multiplicative approximation of the volume of their intersection with the unit hypercube $[0,1]^n$ in time poly$_k(n, 1/\varepsilon, L,L_o)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19809 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Deterministic Volume Estimation of Truncated Hypercubes Gunluk, Kyra Data Structures and Algorithms Computational Geometry We present a deterministic polynomial-time algorithm for estimating the volume of a hypercube intersected by a fixed number of constraints of the type $f(x) \leq b$, where $f$ is the sum of univariate functions that are each nonnegative, monotone, and convex. Such constraints include knapsack and norm-ball constraints. The case of the unit hypercube truncated by a single linear constraint (halfspace) is already #P-hard. Given $k$ such constraints in dimension $n$, with total input length of at most $L$ bits, total output length of at most $L_o$ bits, and an error parameter $\varepsilon > 0$, our algorithm computes a $(1 + \varepsilon)$-multiplicative approximation of the volume of their intersection with the unit hypercube $[0,1]^n$ in time poly$_k(n, 1/\varepsilon, L,L_o)$. |
| title | Deterministic Volume Estimation of Truncated Hypercubes |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2605.19809 |