An analysis of Monte Carlo algorithms for counting problems
The efficiency of Monte Carlo approximations for solving {\#}P-hard counting problems is investigated in this paper. In particular, a necessary condition is derived for a problem to admit of a Monte Carlo algorithm with polynomial time complexity and bounded relative error. Two Monte Carlo procedures are proposed for the approximate solution of the following {\#}P-complete counting problems: given a finite set E and a collection \(\{S_ 1,S_ 2,...,S_ m\}\) of subsets of E, compute the cardinality of the union set \(\cup^{m}_{i=1}S_ i\) (Union Cardinality Problem) or the intersection set \(\cap^{m}_{i=1}S_ i\) (Intersection Cardinality Problem). Tight bounds on the worst-case time complexity of both algorithms are explicitly obtained. It is shown that one of the algorithms solves the union cardinality problem in polynomial time, within any specified accuracy level, provided \(m<4| E|\), the cardinalities of the sets \(S_ i\), \(i=1,2,...,m\), are known in advance and it is possible to select a member of \(S_ i\) in polynomial time. Observe that these requirements are fulfilled in all relevant applications of the union cardinality problem. Finally, a probabilistic analysis of the proposed algorithm for the intersection cardinality problem is developed, assuming a reasonable stochastic model over the instances of the problem. This allows to show that, under mild assumptions on the stochastic parameters, a substantial reduction in running time can be achieved with probability tending to one when the input size grows asymptotically large.
- scientific article; zbMATH DE number 3954144
- Monte-Carlo approximation algorithms for enumeration problems
- A statistical analysis of probabilistic counting algorithms
- scientific article; zbMATH DE number 4162272
- A stochastic approach to counting problems
- scientific article; zbMATH DE number 3878357
- Approximate counting with \(m\) counters: a probabilistic analysis
- scientific article; zbMATH DE number 953025
- Monte Carlo algorithms: Performance analysis for some computer architectures
- scientific article; zbMATH DE number 3466802 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3419161 (Why is no real title available?)
- Monte-Carlo approximation algorithms for enumeration problems
- Network reliability and the factoring theorem
- Randomised algorithms
- Sulla complessita di alcuni problemi di conteggio
- The complexity of computing the permanent
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- Importance sampling the union of rare events with an application to power systems analysis
- Stochastic enumeration with importance sampling
- Monte Carlo approaches to parameterized poker squares
- How many needles are in a haystack, or how to solve \#P-complete counting problems fast
- A Monte Carlo algorithm for a lottery problem
- Using the Monte Carlo method for fast simulation of the number of ``good permutations on the SCIT-4 multiprocessor computer complex
- scientific article; zbMATH DE number 4162272 (Why is no real title available?)
- Stochastic enumeration method for counting NP-hard problems
- scientific article; zbMATH DE number 3954144 (Why is no real title available?)
- Monte-Carlo approximation algorithms for enumeration problems
- scientific article; zbMATH DE number 1057883 (Why is no real title available?)
- Importance sampling for estimating expected values: a heuristic approach for NP-hard interval problems
- Approximate set union via approximate randomization
- Approximate set union via approximate randomization
This page was built for publication: An analysis of Monte Carlo algorithms for counting problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083200)
