Regensburg 2022 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

DY: Fachverband Dynamik und Statistische Physik

DY 44: Poster Session: Statistical Physics and Critical Phenomena

DY 44.16: Poster

Donnerstag, 8. September 2022, 15:00–18:00, P2

Phase transitions for two-stage stochastic minimum spanning tree optimisation problem — •Robert Strassen and Alexander K. Hartmann — Institute of Physics, University of Oldenburg

Phase transitions in classical optimization problems have been studied extensively in statistical physics [1]. Here, we consider two-stage stochastic optimization problems, where the optimization is performed in two different stages, such that in the first stage not all information is available. In particular, we consider the two-stage stochastic minimum spanning tree (MST) problem for undirected graphs with given initial edge costs. In the second stage, one of a set of random scenarios is realized, involving different edge costs. In each stage, edges can be selected such that a spanning tree is finally formed, aiming at a minimum expected total costs. Unlike the conventional MST problem, the two-stage version is generally worts-case “hard” to solve, even though there are problem instances that are “easy”. We investigate numerically [2] the problem by the calculation of bounds and applying several approximation algorithms, including one of Dhamdere et al. [3] on various random ensembles of graphs. Our aim is to find out whether there are phase transitions between typical easy and hard problem phases.

[1] A.K. Hartmann and M. Weigt, Phase Transitions in Optimization Problems, Wiley-VCH, Berlin 2005

[2] A.K. Hartmann, Big Practical Guide to Computer Simulations, World-Scientific, Singapore, 2015

[3] K. Dhamdhere, R. Ravi, M. Singh, IPCO 2005, LNCS 3509, pp. 321-334, (2005)