Name
Abstract | ||
|---|---|---|
We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm. Our computational study indicates that our branch-and-cut algorithm finds optimal solutions for networks with up to 200 nodes within two hours of CPU time, while the heuristic search procedures rapidly find near-optimal solutions for all of the test instances. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10732-007-9027-1 | J. Heuristics |
Keywords | Field | DocType |
Networks,Heuristics,Local search,Genetic algorithms,Branch-and-cut | Mathematical optimization,Distributed minimum spanning tree,Prim's algorithm,K-ary tree,Spanning tree,Artificial intelligence,Mathematics,Kruskal's algorithm,Machine learning,Reverse-delete algorithm,Minimum spanning tree,Search tree | Journal |
Volume | Issue | ISSN |
14 | 1 | 1381-1231 |
Citations | PageRank | References |
7 | 0.61 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruce L. Golden | 1 | 1110 | 176.17 |
| S. Raghavan | 2 | 216 | 16.30 |
| Daliborka Stanojević | 3 | 29 | 2.52 |