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

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

zbMATH Keywords

approximation algorithmvolume computation\#P-hard problemsdeterministic FPTAS

Mathematics Subject Classification ID

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