An FPTAS for the volume of some V -polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
From MaRDI portal
Publication:784479
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)
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
Cites work
- 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?)
- 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^\ast(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
- 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
Cited in
(6)- On the Complexity of Computing the Volume of a Polyhedron
- Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
- Approximating the volume of unions and intersections of high-dimensional geometric objects
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- An FPTAS for the volume computationof 0-1 knapsack polytopes based on approximate convolution integral
- An FPTAS for the volume of some \(\mathcal{V}\)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
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)
