Numerical calibration of Steiner trees (Q1734283)

The authors consider variational problems related to the Steiner tree problem, i.e. one-dimensional models arising in graph theory, shape optimization, optimal transport, and elastoplasticity. The Steiner tree problem is defined as finding the shortest connected set containing given \(n\) points \(\{x_1,\ldots, x_n\}\) in the Euclidean space \(\mathbb{R}^d\). In this paper, a variational approach is proposed to identify an optimal one-dimensional structure of the Steiner tree problem. It was shown that the Steiner tree problem is equivalent to the classical mass-minimization problem with the prescribed boundary, known as Plateau problem. A new calibration algorithm is introduced to establish the minimality of a polyhedral chain. The resulting non-smooth convex optimality problem is solved with the proximal alternating-direction method of multipliers [\textit{A. Chambolle} and \textit{T. Pock}, J. Math. Imaging Vision 40, No. 1, 120--145 (2011, Zbl 1255.68217)]. The calibration technique verified numerically on several examples.