On optimal solutions for the optimal communication spanning tree problem
- Publikationstyp:
- Zeitschriftenaufsatz
- Metadaten:
-
- Autoren
- Sammlungen
- metadata
- ISSN
- 1526-5463
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- Operations research
- Schlüsselwörter
- 330 Wirtschaft
- 330 Economics
- Sprache
- eng
- Paginierung
- Seiten: 413 - 425
- Datum der Veröffentlichung
- 2009
- Herausgeber URL
- http://dx.doi.org/10.1287/opre.1080.0592
- Datum der Datenerfassung
- 2020
- Datum, an dem der Datensatz öffentlich gemacht wurde
- 2020
- Zugang
- Public
- Titel
- On optimal solutions for the optimal communication spanning tree problem
- Ausgabe der Zeitschrift
- 57
Datenquelle: METADATA.UB
- Andere Metadatenquellen:
-
- Autoren
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000265394800012&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1287/opre.1080.0592
- Externe Identifier
- Clarivate Analytics Document Solution ID: 436EG
- ISSN
- 0030-364X
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- OPERATIONS RESEARCH
- Paginierung
- 413 - 425
- Datum der Veröffentlichung
- 2009
- Status
- Published
- Titel
- On Optimal Solutions for the Optimal Communication Spanning Tree Problem
- Sub types
- Article
- Ausgabe der Zeitschrift
- 57
Datenquelle: Web of Science (Lite)
- Abstract
- <jats:p> This paper presents an experimental investigation into the properties of the optimal communication spanning tree (OCST) problem. The OCST problem seeks a spanning tree that connects all the nodes and satisfies their communication requirements at a minimum total cost. The paper compares the properties of random trees to the properties of the best solutions for the OCST problem that are found using an evolutionary algorithm. The results show, on average, that the optimal solution and the minimum spanning tree (MST) share a higher number of links than the optimal solution and a random tree. Furthermore, optimal solutions for OCST problems with randomly chosen distance weights share a higher number of links with an MST than OCST problems with Euclidean distance weights. This intuitive similarity between optimal solutions and MSTs suggests that some heuristic optimization methods for OCST problems might be improved by starting with an MST. Using an MST as a starting solution for a greedy search in the tested cases either improves median running time up to a factor of 10 while finding solutions of the same quality, or increases solution quality up to a factor of 100 while using the same number of search steps in comparison to starting the greedy search from a random tree. Starting a local search, a simulated annealing approach and a genetic algorithm from an MST increases solution quality up to a factor of three in comparison to starting from a random solution. </jats:p>
- Autoren
- DOI
- 10.1287/opre.1080.0592
- eISSN
- 1526-5463
- ISSN
- 0030-364X
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- Operations Research
- Sprache
- en
- Paginierung
- 413 - 425
- Datum der Veröffentlichung
- 2009
- Status
- Published
- Herausgeber
- Institute for Operations Research and the Management Sciences (INFORMS)
- Herausgeber URL
- http://dx.doi.org/10.1287/opre.1080.0592
- Datum der Datenerfassung
- 2023
- Titel
- On Optimal Solutions for the Optimal Communication Spanning Tree Problem
- Ausgabe der Zeitschrift
- 57
Datenquelle: Crossref
- Autoren
- DOI
- 10.1287/opre.1080.0592
- Zeitschrift
- Oper. Res.
- Artikelnummer
- 2
- Paginierung
- 413 - 425
- Datum der Veröffentlichung
- 2009
- Titel
- On Optimal Solutions for the Optimal Communication Spanning Tree Problem.
- Ausgabe der Zeitschrift
- 57
Datenquelle: DBLP
- Abstract
- This paper presents an experimental investigation into the properties of the optimal communication spanning tree (OCST) problem. The OCST problem seeks a spanning tree that connects all the nodes and satisfies their communication requirements at a minimum total cost. The paper compares the properties of random trees to the properties of the best solutions for the OCST problem that are found using an evolutionary algorithm. The results show, on average, that the optimal solution and the minimum spanning tree (MST) share a higher number of links than the optimal solution and a random tree. Furthermore, optimal solutions for OCST problems with randomly chosen distance weights share a higher number of links with an MST than OCST problems with Euclidean distance weights. This intuitive similarity between optimal solutions and MSTs suggests that some heuristic optimization methods for OCST problems might be improved by starting with an MST. Using an MST as a starting solution for a greedy search in the tested cases either improves median running time up to a factor of 10 while finding solutions of the same quality, or increases solution quality up to a factor of 100 while using the same number of search steps in comparison to starting the greedy search from a random tree. Starting a local search, a simulated annealing approach and a genetic algorithm from an MST increases solution quality up to a factor of three in comparison to starting from a random solution.
- Addresses
- Department of Information Systems, University of Mainz, Mainz 55099, Germany
- Autoren
- Ausgabe der Veröffentlichung
- 2
- Schlüsselwörter
- networks/graphs
- tree algorithms
- communications
- topological network design
- simulation
- statistical analysis
- Paginierung
- 413 - 425
- Datum der Veröffentlichung
- 2009
- Titel
- On Optimal Solutions for the Optimal Communication Spanning Tree Problem
- Ausgabe der Zeitschrift
- 57
Datenquelle: RePEc
- Beziehungen:
- Eigentum von