Parts | Days | Selection | Search | Downloads | Help
DY: Dynamik und Statistische Physik
DY 10: Allgemeine Statistische Physik I
DY 10.4: Talk
Tuesday, March 18, 1997, 11:15–11:30, R1
Searching for Backbones - Ein effizienter paralleler Algorithmus für das Traveling Salesman Problem — •J. Schneider1, Ch. Froschhammer1, I. Morgenstern1, Th. Hußlein1, and J. M. Singer2 — 1Institut für Theoretische Physik, Universität Regensburg, Universitätsstr. 31, D-93053 Regensburg — 2Physikinstitut, Universität Zürich, CH-8057 Zürich
The Traveling Salesman Problem (TSP) plays an important role in Operations Research, Applied Mathematics and Computational Physics. We investigated it using a stochastic approach. Studying several solutions of a special TSP we found that many parts of a good solution are the same in all other good solutions for this problem. We discuss an efficient parallel method to reduce the TSP to a smaller one by finding these backbones and eliminating them to get even better solutions in a very short time and a few observables of interest corresponding to this parallel approach [1].
[1] J. Schneider, Ch. Froschhammer, I. Morgenstern, Th. Husslein, J. M. Singer, Computer Physics Communications 96 (2/3) (1996) 173–188