An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
From MaRDI portal
Publication:727987
DOI10.1007/S00453-015-0096-5zbMATH Open1355.68291OpenAlexW2172970418MaRDI QIDQ727987FDOQ727987
Authors: Ei Ando, Shuji Kijima 
Publication date: 21 December 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0096-5
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- 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
- 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 colorings of a graph
- Computing the volume is difficult
- An FPTAS for the volume computationof 0-1 knapsack polytopes based on approximate convolution integral
- A simple FPTAS for counting edge covers
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)
