Name
Abstract | ||
|---|---|---|
We describe improvements to Smith's branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in R^d. Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by ''merging'' a new terminal node with each edge in the current Steiner tree. For a given topology we use a conic formulation for the problem of locating the Steiner points to obtain a rigorous lower bound on the minimal tree length. We also show how to obtain lower bounds on the child problems at a given node without actually computing the minimal Steiner trees associated with the child topologies. These lower bounds reduce the number of children created and also permit the implementation of a ''strong branching'' strategy that varies the order in which the terminal nodes are added. Computational results demonstrate substantial gains compared to Smith's original algorithm. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.disopt.2007.08.006 | Discrete Optimization |
Keywords | Field | DocType |
steiner tree,b tree,steiner minimal tree,terminal node,euclidean steiner problem,strong branching.,steiner point,lower bound,branch and bound,minimal steiner tree,full steiner,strong branching,improved algorithm,euclidean d-space,minimal tree length,current steiner tree,new terminal node | Upper and lower bounds,Steiner tree problem,B-tree,Euclidean geometry,Branching (version control),Discrete mathematics,Combinatorics,Mathematical optimization,Branch and bound,Algorithm,Network topology,Conic section,Mathematics | Journal |
Volume | Issue | ISSN |
5 | 2 | Discrete Optimization |
Citations | PageRank | References |
8 | 0.65 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcia Fampa | 1 | 58 | 11.69 |
| Kurt M. Anstreicher | 2 | 633 | 86.40 |