Geodesic
The influence of random number generators on graph partitioning algorithms
Electronic transactions on numerical analysis, Tome 21 (2005), pp. 125-133
Zbl   EuDML
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 
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/
@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},
     year = {2005},
     volume = {21},
     zbl = {1112.68107},
     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
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
%U http://geodesic.mathdoc.fr/item/ETNA_2005__21__a1/
%G en
%F ETNA_2005__21__a1