Monte-Carlo approximation algorithms for enumeration problems
From MaRDI portal
Publication:3834934
DOI10.1016/0196-6774(89)90038-2zbMath0678.65001OpenAlexW2094500233MaRDI QIDQ3834934
Neal Madras, Michael Luby, Richard M. Karp
Publication date: 1989
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(89)90038-2
statistical physicsestimateMonte Carlo algorithmsenumeration problemsnetwork reliabilityphysical chemistryself-adjusting coverage algorithm theoremzero-one estimator theorem
Related Items
Completeness Results for Counting Problems with Easy Decision, An analysis of Monte Carlo algorithms for counting problems, Sequential Monte Carlo for counting vertex covers in general graphs, The structure and complexity of Nash equilibria for a selfish routing game, On some approximation problems concerning sparse polynomials over finite fields, Parameterized counting matching and packing: a family of hard problems that admit FPTRAS, Testing the shift-equivalence of polynomials using quantum machines, A quasi-polynomial-time algorithm for sampling words from a context-free language, DNF sparsification and a faster deterministic counting algorithm, On deterministic approximation of DNF, A Bayesian approach to relevance in game playing, Inverse Sampling for Nonasymptotic Sequential Estimation of Bounded Variable Means, On the connection between interval size functions and path counting, On the random generation and counting of matchings in dense graphs, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines., An optimal approximation algorithm for Bayesian inference, An OpenCL implementation of a forward sampling algorithm for CP-logic, A Bernoulli mean estimate with known relative error distribution, The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk., Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT, Approximate inference in Bayesian networks: parameterized complexity results, On Counting Parameterized Matching and Packing, Lower bounds for sampling algorithms for estimating the average, Open-world probabilistic databases: semantics, algorithms, complexity, Self-testing algorithms for self-avoiding walks, The worm process for the Ising model is rapidly mixing, A genetic algorithm for joint replenishment based on the exact inventory cost, Counting curves and their projections, Generalized loop‐erased random walks and approximate reachability, Approximating the permanent of graphs with large factors, Probabilistic verification and approximation, ARITHMETIC OF POTTS MODEL HYPERSURFACES, Queries and materialized views on probabilistic databases, Not all FPRASs are equal: demystifying FPRASs for DNF-counting, Approximating the volume of unions and intersections of high-dimensional geometric objects, Approximate set union via approximate randomization, Approximate set union via approximate randomization, Maximum box problem on stochastic points, Unnamed Item, On counting 3-D matchings of size \(k\), Approximate weighted model integration on DNF structures, Data source selection for approximate query, POWER INDICES AND THE MEASUREMENT OF CONTROL IN CORPORATE STRUCTURES, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Probability estimation via policy restrictions, convexification, and approximate sampling, Critical exponents, hyperscaling, and universal amplitude ratios for two- and three-dimensional self-avoiding walks., Approximating the number of monomer-dimer coverings of a lattice., Self-testing/correcting with applications to numerical problems, On sparse approximations to randomized strategies and convex combinations
