An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
DOI10.1016/j.tcs.2020.05.029zbMath1455.68273OpenAlexW3026541330MaRDI QIDQ784479
Publication date: 3 August 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.05.029
Analysis of algorithms (68W40) (n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- A geometric inequality and the complexity of computing volume
- Computing the volume is difficult
- A fully polynomial-time approximation scheme for approximating a sum of random variables
- An FPTAS for the volume of some \(\mathcal{V}\)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
- Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
- A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
- Counting independent sets up to the tree threshold
- Bypassing KLS
- The problem of calculating the volume of a polyhedron is enumerably hard
- Approximate counting by dynamic programming
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- On the Complexity of Computing the Volume of a Polyhedron
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Reducibility among Combinatorial Problems
- Near-optimal deterministic algorithms for volume computation via M-ellipsoids
- A Simple FPTAS for Counting Edge Covers
- An FPTAS for #Knapsack and Related Counting Problems
- Correlation Decay up to Uniqueness in Spin Systems
- Approximate Counting via Correlation Decay in Spin Systems
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
