Geodesic
Approximate Counting via the Poisson-Laplace-Mellin Method
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

Voir la notice de l'article provenant de la source Episciences

Approximate counting is an algorithm that provides a count of a huge number of objects within an error tolerance. The first detailed analysis of this algorithm was given by Flajolet. In this paper, we propose a new analysis via the Poisson-Laplace-Mellin approach, a method devised for analyzing shape parameters of digital search trees in a recent paper of Hwang et al. Our approach yields a different and more compact expression for the periodic function from the asymptotic expansion of the variance. We show directly that our expression coincides with the one obtained by Flajolet. Moreover, we apply our method to variations of approximate counting, too. 
@article{DMTCS_2012_special_262_a1,
     author = {Fuchs, Michael and Lee, Chung-Kuei and Prodinger, Helmut},
     title = {Approximate {Counting} via the {Poisson-Laplace-Mellin} {Method}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.2980},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2980/}
}
TY  - JOUR
AU  - Fuchs, Michael
AU  - Lee, Chung-Kuei
AU  - Prodinger, Helmut
TI  - Approximate Counting via the Poisson-Laplace-Mellin Method
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2980/
DO  - 10.46298/dmtcs.2980
LA  - en
ID  - DMTCS_2012_special_262_a1
ER  - 
%0 Journal Article
%A Fuchs, Michael
%A Lee, Chung-Kuei
%A Prodinger, Helmut
%T Approximate Counting via the Poisson-Laplace-Mellin Method
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2980/
%R 10.46298/dmtcs.2980
%G en
%F DMTCS_2012_special_262_a1
Fuchs, Michael; Lee, Chung-Kuei; Prodinger, Helmut. Approximate Counting via the Poisson-Laplace-Mellin Method. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.2980. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2980/

Cité par Sources :