A deterministic polynomial-time approximation scheme for counting knapsack solutions
From MaRDI portal
Abstract: Given n elements with nonnegative integer weights w1,..., wn and an integer capacity C, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most the given capacity. We give a deterministic algorithm that estimates the number of solutions to within relative error 1+-eps in time polynomial in n and 1/eps (fully polynomial approximation scheme). More precisely, our algorithm takes time O(n^3 (1/eps) log (n/eps)). Our algorithm is based on dynamic programming. Previously, randomized polynomial time approximation schemes were known first by Morris and Sinclair via Markov chain Monte Carlo techniques, and subsequently by Dyer via dynamic programming and rejection sampling.
Recommendations
- A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
- scientific article; zbMATH DE number 6861894
- A new fully polynomial time approximation scheme for the Knapsack problem
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- scientific article; zbMATH DE number 1418266
- A pseudo-polynomial time algorithm for solving the knapsack problem in polynomial space
- scientific article; zbMATH DE number 1182767
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
- Counting Solutions of Knapsack Constraints
- The fully polynomial approximation algorithm for the 0-1 knapsack problem
Cited in
(23)- Faster FPTASes for counting and random generation of knapsack solutions
- A faster FPTAS for counting two-rowed contingency tables
- scientific article; zbMATH DE number 7401920 (Why is no real title available?)
- Approximate counting by dynamic programming
- Approximately counting approximately-shortest paths in directed acyclic graphs
- A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
- An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
- An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
- Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
- Approximate counting via correlation decay in spin systems
- Constant-time approximation algorithms for the knapsack problem
- A fully polynomial-time approximation scheme for approximating a sum of random variables
- scientific article; zbMATH DE number 6861894 (Why is no real title available?)
- 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
- Approximate \#knapsack computations to count semi-fair allocations
- Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
- Faster FPTASes for counting and random generation of knapsack solutions
- A faster FPTAS for \#Knapsack
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
- Strongly polynomial FPTASes for monotone dynamic programs
This page was built for publication: A deterministic polynomial-time approximation scheme for counting knapsack solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2903521)
