TY - JOUR AU - Burt, Christina AU - Costa, Alysson AU - Ras, Charl PY - 2018/11/19 Y2 - 2024/03/29 TI - Algorithms for the power-p Steiner tree problem in the Euclidean plane JF - Revista de Informática Teórica e Aplicada JA - RITA VL - 25 IS - 4 SE - Special Issue - Exact and Heuristic Solutions for Optimization Problems DO - 10.22456/2175-2745.80525 UR - https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_28 SP - 28-42 AB - We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost of an edge is its length to the power of $p$ (where $p\geq 1$), and the cost of a network is the sum of all edge costs. We propose two heuristics: a ``beaded" minimum spanning tree heuristic; and a heuristic which alternates between minimum spanning tree construction and a local fixed topology minimisation procedure for locating the Steiner points. We show that the performance ratio $\kappa$ of the beaded-MST heuristic satisfies $\sqrt{3}^{p-1}(1+2^{1-p})\leq \kappa\leq 3(2^{p-1})$. We then provide two mixed-integer nonlinear programming formulations for the problem, and extend several important geometric properties into valid inequalities. Finally, we combine the valid inequalities with warm-starting and preprocessing to obtain computational improvements for the $p=2$ case.<br /><br /> ER -