Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces

Rasmus Fonseca; Marcus Brazil; Pawel Winter; Martin Zachariasen

Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces

Rasmus Fonseca, Marcus Brazil, Pawel Winter, Martin Zachariasen

Datalogisk Institut

39 Downloads (Pure)

Abstract

The Euclidean Steiner tree problem asks for a network of minimum total length interconnecting a finite set of points in d-dimensional space. For d ≥ 3, only one practical algorithmic approach exists for this problem --- proposed by Smith in 1992. A number of refinements of Smith's algorithm have increased the range of solvable problems a little, but it is still infeasible to solve problem instances with more than around 17 terminals. In this paper we firstly propose some additional improvements to Smith's algorithm. Secondly, we propose a new algorithmic paradigm called branch enumeration. Our experiments show that branch enumeration has similar performance as an optimized version of Smith's algorithm; furthermore, we argue that branch enumeration has the potential to push the boundary of solvable problems further.

Originalsprog	Engelsk
Publikationsdato	2014
Antal sider	20
Status	Udgivet - 2014
Begivenhed	11th DIMACS Implementation Challenge - ICERM, Providence, USA Varighed: 4 dec. 2014 → 5 dec. 2014 Konferencens nummer: 11

Konference

Konference	11th DIMACS Implementation Challenge
Nummer	11
Lokation	ICERM
Land/Område	USA
By	Providence
Periode	04/12/2014 → 05/12/2014

Emneord

Det Natur- og Biovidenskabelige Fakultet

Adgang til dokumentet

Fonseca_2015_Faster_exact_algorithmsIndsendt manuskript, 453 KB

http://dimacs11.zib.de/workshop/FonsecaBrazilWinterZachariasen.pdf

Citationsformater

@conference{df3345c1077d42fd87ba161e208d42c9,

title = "Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces",

abstract = "The Euclidean Steiner tree problem asks for a network of minimum total length interconnecting a finite set of points in d-dimensional space. For d ≥ 3, only one practical algorithmic approach exists for this problem --- proposed by Smith in 1992. A number of refinements of Smith's algorithm have increased the range of solvable problems a little, but it is still infeasible to solve problem instances with more than around 17 terminals. In this paper we firstly propose some additional improvements to Smith's algorithm. Secondly, we propose a new algorithmic paradigm called branch enumeration. Our experiments show that branch enumeration has similar performance as an optimized version of Smith's algorithm; furthermore, we argue that branch enumeration has the potential to push the boundary of solvable problems further.",

keywords = "Faculty of Science, Steiner tree problem, d-dimensional Euclidean space, exact algorithm, computational study",

author = "Rasmus Fonseca and Marcus Brazil and Pawel Winter and Martin Zachariasen",

year = "2014",

language = "English",

note = "11th DIMACS Implementation Challenge ; Conference date: 04-12-2014 Through 05-12-2014",

}

TY - CONF

T1 - Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces

AU - Fonseca, Rasmus

AU - Brazil, Marcus

AU - Winter, Pawel

AU - Zachariasen, Martin

N1 - Conference code: 11

PY - 2014

Y1 - 2014

N2 - The Euclidean Steiner tree problem asks for a network of minimum total length interconnecting a finite set of points in d-dimensional space. For d ≥ 3, only one practical algorithmic approach exists for this problem --- proposed by Smith in 1992. A number of refinements of Smith's algorithm have increased the range of solvable problems a little, but it is still infeasible to solve problem instances with more than around 17 terminals. In this paper we firstly propose some additional improvements to Smith's algorithm. Secondly, we propose a new algorithmic paradigm called branch enumeration. Our experiments show that branch enumeration has similar performance as an optimized version of Smith's algorithm; furthermore, we argue that branch enumeration has the potential to push the boundary of solvable problems further.

AB - The Euclidean Steiner tree problem asks for a network of minimum total length interconnecting a finite set of points in d-dimensional space. For d ≥ 3, only one practical algorithmic approach exists for this problem --- proposed by Smith in 1992. A number of refinements of Smith's algorithm have increased the range of solvable problems a little, but it is still infeasible to solve problem instances with more than around 17 terminals. In this paper we firstly propose some additional improvements to Smith's algorithm. Secondly, we propose a new algorithmic paradigm called branch enumeration. Our experiments show that branch enumeration has similar performance as an optimized version of Smith's algorithm; furthermore, we argue that branch enumeration has the potential to push the boundary of solvable problems further.

KW - Faculty of Science

KW - Steiner tree problem

KW - d-dimensional Euclidean space

KW - exact algorithm

KW - computational study

M3 - Paper

T2 - 11th DIMACS Implementation Challenge

Y2 - 4 December 2014 through 5 December 2014

ER -

Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces

Abstract

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater