A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
From MaRDI portal
Publication:2903521
DOI10.1137/11083976XzbMath1253.68182arXiv1008.1687OpenAlexW1985985425MaRDI QIDQ2903521
Eric Vigoda, Daniel Štefanković, Santosh Vempala
Publication date: 10 August 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1008.1687
Related Items (15)
A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy ⋮ Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ Faster FPTASes for counting and random generation of knapsack solutions ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ A Faster FPTAS for #Knapsack ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ A fully polynomial-time approximation scheme for approximating a sum of random variables ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier ⋮ Approximately counting approximately-shortest paths in directed acyclic graphs
This page was built for publication: A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
