| dc.creator | Burt, Christina | |
| dc.creator | Costa, Alysson | |
| dc.creator | Ras, Charl | |
| dc.date | 2018-11-19 | |
| dc.date.accessioned | 2022-10-04T22:27:15Z | |
| dc.date.available | 2022-10-04T22:27:15Z | |
| dc.identifier | https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_28 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/3870378 | |
| dc.description | 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. | en-US |
| dc.format | application/pdf | |
| dc.language | eng | |
| dc.publisher | Instituto de Informática - Universidade Federal do Rio Grande do Sul | en-US |
| dc.relation | https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_28/pdf | |
| dc.rights | Copyright (c) 2018 Christina Burt, Alysson Costa, Charl Ras | pt-BR |
| dc.source | Revista de Informática Teórica e Aplicada; Vol. 25 No. 4 (2018); 28-42 | en-US |
| dc.source | Revista de Informática Teórica e Aplicada; v. 25 n. 4 (2018); 28-42 | pt-BR |
| dc.source | 2175-2745 | |
| dc.source | 0103-4308 | |
| dc.subject | Steiner tree problem | en-US |
| dc.subject | Power-p | en-US |
| dc.subject | Mixed-integer formulations | en-US |
| dc.subject | Heuristics | en-US |
| dc.title | Algorithms for the power-p Steiner tree problem in the Euclidean plane | en-US |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
