Approximate counting by dynamic programming
From MaRDI portal
Publication:3581284
DOI10.1145/780542.780643zbMath1192.90242OpenAlexW2003554015MaRDI QIDQ3581284
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
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Dynamic programming (90C39)
Related Items (24)
Knapsack polytopes: a survey ⋮ Completeness Results for Counting Problems with Easy Decision ⋮ Sequential Monte Carlo for counting vertex covers in general graphs ⋮ A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy ⋮ Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra ⋮ Rapid calculation of exact cell bounds for contingency tables from conditional frequencies ⋮ On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries ⋮ Faster FPTASes for counting and random generation of knapsack solutions ⋮ On computing probabilistic abductive explanations ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard ⋮ Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries ⋮ A Faster FPTAS for #Knapsack ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ Stochastic enumeration method for counting trees ⋮ A fully polynomial-time approximation scheme for approximating a sum of random variables ⋮ Unnamed Item ⋮ Random walks on the vertices of transportation polytopes with constant number of sources ⋮ The Complexity of Computing the Optimal Composition of Differential Privacy ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Graph classes and the switch Markov chain for matchings ⋮ Randomization methods for assessing data analysis results on real‐valued matrices ⋮ Estimating the probability of meeting a deadline in schedules and plans ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
This page was built for publication: Approximate counting by dynamic programming
