Deterministic Volume Estimation of Truncated Hypercubes
For theoretical computer scientists and optimization researchers, it provides the first deterministic polynomial-time algorithm for a class of volume estimation problems that includes #P-hard cases, though the number of constraints is fixed.
The paper presents a deterministic polynomial-time algorithm for estimating the volume of a hypercube intersected by a fixed number of constraints (e.g., knapsack, norm-ball), achieving a (1+ε)-multiplicative approximation in time polynomial in n, 1/ε, and input/output lengths, despite the #P-hardness of the single-linear-constraint case.
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)$.