Approximate counting by dynamic programming

DOI10.1145/780542.780643zbMath1192.90242MaRDI QIDQ3581284

Martin Dyer

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780643

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

90C39: Dynamic programming

Related Items

Unnamed Item, Randomization methods for assessing data analysis results on real‐valued matrices, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, A Faster FPTAS for #Knapsack, Completeness Results for Counting Problems with Easy Decision, On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries, Graph classes and the switch Markov chain for matchings, On computing probabilistic abductive explanations, Discrete Optimal Transport with Independent Marginals is #P-Hard, Sequential Monte Carlo for counting vertex covers in general graphs, A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy, Rapid calculation of exact cell bounds for contingency tables from conditional frequencies, Stochastic enumeration method for counting trees, On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes, Knapsack polytopes: a survey, A fully polynomial-time approximation scheme for approximating a sum of random variables, A faster FPTAS for counting two-rowed contingency tables, Estimating the probability of meeting a deadline in schedules and plans, Faster FPTASes for counting and random generation of knapsack solutions, The Complexity of Computing the Optimal Composition of Differential Privacy, Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra, Random walks on the vertices of transportation polytopes with constant number of sources