An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
From MaRDI portal
(Redirected from Publication:727987)
Recommendations
- 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
- An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
- Faster FPTASes for counting and random generation of knapsack solutions
- Practical polytope volume approximation
Cites work
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 3980484 (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 computationof 0-1 knapsack polytopes based on approximate convolution integral
- 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 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
- On the Complexity of Computing the Volume of a Polyhedron
- Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
Cited in
(6)- 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 Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
- 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
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
This page was built for publication: An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727987)
