Solving the prize-collecting Euclidean Steiner tree problem
Web of Science
AuthorWhittle, D; Brazil, M; Grossman, PA; Rubinstein, JH; Thomas, DA
Source TitleInternational Transactions in Operational Research
University of Melbourne Author/sThomas, Doreen; Grossman, Peter; Brazil, Marcus; Rubinstein, Joachim; Whittle, David
AffiliationSchool of Mathematics and Statistics
Electrical and Electronic Engineering
Document TypeJournal Article
CitationsWhittle, D., Brazil, M., Grossman, P. A., Rubinstein, J. H. & Thomas, D. A. (2020). Solving the prize-collecting Euclidean Steiner tree problem. INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, https://doi.org/10.1111/itor.12853.
Access StatusThis item is currently not available from this repository
The prize‐collecting Euclidean Steiner tree (PCEST) problem is a generalization of the well‐known Euclidean Steiner tree (EST) problem. All points given in an EST problem instance are connected by the shortest possible network in a solution. A solution can include additional points called Steiner points. A PCEST problem instance differs from an EST problem instance by the addition of weights for each given point. A PCEST solution connects a subset of the given points in order to maximize the net value of the network (the sum of the selected point weights, less than the length of the network). We present an algorithmic framework for solving the PCEST problem. Included in the framework are efficient methods to determine subsets of points that must be in every solution, and subsets of points that cannot be in any solution. Also included are methods to generate and concatenate full Steiner trees.
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References