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-5zbMath1355.68291OpenAlexW2172970418MaRDI QIDQ727987
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (3)
Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
Cites Work
- Unnamed Item
- Unnamed Item
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- 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
- 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
- An FPTAS for the Volume Computationof 0-1 Knapsack Polytopes Based on Approximate Convolution Integral
- 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
- 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 computation of 0-1 knapsack polytopes based on approximate convolution
