Solving the prize‐collecting Euclidean Steiner tree problem
| Autor: | P. A. Grossman, J. Hyam Rubinstein, Marcus Brazil, David Whittle, Doreen A. Thomas |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
Generalization Strategy and Management 0211 other engineering and technologies Value (computer science) 02 engineering and technology Management Science and Operations Research Steiner tree problem Computer Science Applications Combinatorics symbols.namesake Management of Technology and Innovation Euclidean geometry 0202 electrical engineering electronic engineering information engineering symbols Order (group theory) 020201 artificial intelligence & image processing Point (geometry) Business and International Management Mathematics |
| Zdroj: | International Transactions in Operational Research. 29:1479-1501 |
| ISSN: | 1475-3995 0969-6016 |
| DOI: | 10.1111/itor.12853 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|