An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes (Q784479)

A \(\mathcal{V} \)-polytope is a convex hull of a finite point set in \(\mathbb{R}^n\). A particular type of \(\mathcal{V} \)-polytope, called ``knapsack dual polytope'' is defined as \(P_{a}=\text{conv}\{\pm e_1, \pm e_2, ..., \pm e_n, a\}\), \(a\in \mathbb{Z}^n_{\geq 0}\). The authors constructively prove the following theorem: For any \(\varepsilon\), \((0 <\varepsilon <1)\), there is a deterministic algorithm that computes \(\hat{V}\) satisfying \(|1- \frac{\text{Vol}(P_a)}{\hat{V}}| \leq \varepsilon\) in \(O(n^{10}\varepsilon^{-6})\) time. This is the first result on designing a fully polynomial time approximation scheme for computing the volume of a \(\mathcal{V} \)-polytope, which is known to be \#P-hard.