An FPTAS for the volume of some V -polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
DOI10.1016/J.TCS.2020.05.029zbMATH Open1455.68273OpenAlexW3026541330MaRDI QIDQ784479FDOQ784479
Authors: Ei Ando, Shuji Kijima 
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
Recommendations
- 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
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) (n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55)
Cites Work
- Reducibility among combinatorial problems
- Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Title not available (Why is that?)
- An FPTAS for #Knapsack and Related Counting Problems
- Counting independent sets up to the tree threshold
- Correlation decay up to uniqueness in spin systems
- Approximate counting via correlation decay in spin systems
- A geometric inequality and the complexity of computing volume
- Title not available (Why is that?)
- A fully polynomial-time approximation scheme for approximating a sum of random variables
- On the Complexity of Computing the Volume of a Polyhedron
- Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
- Approximate counting by dynamic programming
- Title not available (Why is that?)
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Correlation decay and deterministic FPTAS for counting list-colorings of a graph
- Computing the volume is difficult
- The problem of calculating the volume of a polyhedron is enumerably hard
- A simple FPTAS for counting edge covers
- 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
- Title not available (Why is that?)
- Near-optimal deterministic algorithms for volume computation via M-ellipsoids
Cited In (6)
- On the Complexity of Computing the Volume of a Polyhedron
- 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 computation of 0-1 knapsack polytopes based on approximate convolution
- Approximating the volume of unions and intersections of high-dimensional geometric objects
- 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
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)
