Geodesic
The influence of random number generators on graph partitioning algorithms
Electronic transactions on numerical analysis, Tome 21 (2005), pp. 125-133
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},
     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
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/