0000000000132208
AUTHOR
Ingo Morgenstern
Influence of rounding errors on the quality of heuristic optimization algorithms
Abstract Search space smoothing and related heuristic optimization algorithms provide an alternative approach to simulated annealing and its variants: while simulated annealing traverses barriers in the energy landscape at finite temperatures, search space smoothing intends to remove these barriers, so that a greedy algorithm is sufficient to find the global minimum. Several formulas for smoothing the energy landscape have already been applied, one of them making use of the finite numerical precision on a computer. In this paper, we thoroughly investigate the effect of finite numerical accuracy on the quality of results achieved with heuristic optimization algorithms. We present computation…
On the problem of finding a suitable distribution of students to universities in Germany
For many years, the problem of how to distribute students to the various universities in Germany according to the preferences of the students has remained unsolved. Various approaches, like the centralized method to let a central agency organize the distribution to the various universities or the decentralized method to let the students apply directly at their preferred universities, turned out to lead to a significant fraction of frustrated students ending up at universities not being on their preference list or even not having a place to study at all. With our centralized approach, we are able to decrease the fraction of frustrated students as well as the bureaucratic expenses for applica…
Numerical simulations and exactly soluble spin-glass models.
Some general arguments based on recent numerical work are presented to explain the different behavior of short-range, random-bond and long-range, random-site spin glasses. We then analyze an exactly soluble spin-glass model, which may be solved without replicas, and show that, except for the absence of microscopic metastable states, its main features are consistent with the long-range picture.