An FPTAS for the volume of some V -polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
(n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40)
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.
- An FPTAS for the volume of some \(\mathcal{V}\)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
- An FPTAS for the volume computationof 0-1 knapsack polytopes based on approximate convolution integral
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- Approximating the volume of unions and intersections of high-dimensional geometric objects
- On the Complexity of Computing the Volume of a Polyhedron
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- A fully polynomial-time approximation scheme for approximating a sum of random variables
- A geometric inequality and the complexity of computing volume
- A random polynomial-time algorithm for approximating the volume of convex bodies
- A simple FPTAS for counting edge covers
- An FPTAS for #Knapsack and Related Counting Problems
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- An FPTAS for the volume of some \(\mathcal{V}\)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
- Approximate counting by dynamic programming
- Approximate counting via correlation decay in spin systems
- Bypassing KLS: Gaussian cooling and an O^(n^3) volume algorithm
- Computing the volume is difficult
- Correlation decay and deterministic FPTAS for counting list-colorings of a graph
- Correlation decay up to uniqueness in spin systems
- Counting independent sets up to the tree threshold
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- scientific article; zbMATH DE number 431987 (Why is no real title available?)
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- Near-optimal deterministic algorithms for volume computation via M-ellipsoids
- On the Complexity of Computing the Volume of a Polyhedron
- Reducibility among combinatorial problems
- Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
- The problem of calculating the volume of a polyhedron is enumerably hard
- The volume of a crosspolytope truncated by a halfspace
- An FPTAS for the volume of some \(\mathcal{V}\)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
- An FPTAS for the volume computationof 0-1 knapsack polytopes based on approximate convolution integral
- Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
- On the Complexity of Computing the Volume of a Polyhedron
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- Approximating the volume of unions and intersections of high-dimensional geometric objects
This page was built for publication: An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q784479)
