Geodesic
The influence of random number generators on graph partitioning algorithms
Electronic transactions on numerical analysis, Tome 21 (2005), pp. 125-133.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Many modern heuristic algorithms rely at least in some part on random numbers. Using graph partitioning algorithms as an example, we demonstrate the often underestimated influence of these random-number generators on the result of the heuristic algorithms. Even methods that rely on random numbers mostly as a tiebreaking tool can deliver very different results depending only on the starting value of the pseudo-random number generator.
Classification : 05C85, 90C59, 94C15, 65Y99, 68R10
Keywords: graph partitioning, heuristic algorithms, pseudo random-number generator 
@article{ETNA_2005__21__a1,
     author = {Elsner, Ulrich},
     title = {The influence of random number generators on graph partitioning algorithms},
     journal = {Electronic transactions on numerical analysis},
     pages = {125--133},
     publisher = {mathdoc},
     volume = {21},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2005__21__a1/}
}
TY  - JOUR
AU  - Elsner, Ulrich
TI  - The influence of random number generators on graph partitioning algorithms
JO  - Electronic transactions on numerical analysis
PY  - 2005
SP  - 125
EP  - 133
VL  - 21
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ETNA_2005__21__a1/
LA  - en
ID  - ETNA_2005__21__a1
ER  - 
%0 Journal Article
%A Elsner, Ulrich
%T The influence of random number generators on graph partitioning algorithms
%J Electronic transactions on numerical analysis
%D 2005
%P 125-133
%V 21
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ETNA_2005__21__a1/
%G en
%F ETNA_2005__21__a1
Elsner, Ulrich. The influence of random number generators on graph partitioning algorithms. Electronic transactions on numerical analysis, Tome 21 (2005), pp. 125-133. http://geodesic.mathdoc.fr/item/ETNA_2005__21__a1/