Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” e in the length of an approximate Steiner tree, in terms of the maximum deviation d of an interior angle of the tree from 120°. Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between e and d, and make a conjecture which, if true, would somewhat strengthen our bounds on the error. J. H. Rubinstein, J. Weng: Research supported by the Australian Research Council N. Wormald: Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was in the Department of Mathematics and Statistics, University of Melbourne     

Optimal Relay Location for Resource-limited Energy-efficient Wireless Communication

In the design of wireless networks, techniques for improving energy efficiency and extending network lifetime have great importance, particularly for defense and civil/rescue applications where resupplying transmitters with new batteries is not feasible. In this paper we study a method for improving the lifetime of wireless networks by minimizing the length of the longest edge in the interconnecting tree by deploying additional relay nodes at specific locations. This optimization problem, known as the Bottleneck Steiner Tree Problem (BSTP), asks to find a Steiner tree for n terminals with at most k Steiner points such that the length of the longest edge in the tree is minimized. We present a ratio- polynomial time approximation algorithm for BSTP, where is an arbitrary positive number.     

Gradient-constrained discounted Steiner trees II: optimally locating a discounted Steiner point

A gradient-constrained discounted Steiner tree is a network interconnecting given set of nodes in Euclidean space where the gradients of the edges are all no more than an upper bound which defines the maximum gradient. In such a tree, the costs are associated with its edges and values are associated with nodes and are discounted over time. In this paper, we study the problem of optimally locating a single Steiner point in the presence of the gradient constraint in a tree so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An edge in the tree is labelled as a b edge, or a m edge, or an f edge if the gradient between its endpoints is greater than, or equal to, or less than the maximum gradient respectively. The set of edge labels at a discounted Steiner point is called its labelling. The optimal location of the discounted Steiner point is obtained for the labellings that can occur in a gradient-constrained discounted Steiner tree. In this paper, we propose the gradient-constrained discounted Steiner point algorithm to optimally locate the discounted Steiner point in the presence of a gradient constraint in a network. This algorithm is applied to a case study. This problem occurs in underground mining, where we focus on the optimization of underground mine access to obtain maximum NPV in the presence of a gradient constraint. The gradient constraint defines the navigability conditions for trucks along the underground tunnels.     

Approximations for Steiner Trees with Minimum Number of Steiner Points

Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.     

Approximations for two variants of the Steiner tree problem in the Euclidean plane {\mathbb{R}^2}

Given n terminals in the Euclidean plane and a positive constant l, find a Steiner tree T interconnecting all terminals with the minimum total cost of Steiner points and a specific material used to construct all edges in T such that the Euclidean length of each edge in T is no more than l. In this paper, according to the cost b of each Steiner point and the different costs of some specific materials with the different lengths, we study two variants of the Steiner tree problem in the Euclidean plane as follows: (1) If a specific material to construct all edges in such a Steiner tree has its infinite length and the cost of per unit length of such a specific material used is c ₁, the objective is to minimize the total cost of the Steiner points and such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_1+ c_1 \cdot \sum_{e \in T} w(e)\}}$ , where T is a Steiner tree constructed, k ₁ is the number of Steiner points and w(e) is the length of part cut from such a specific material to construct edge e in T, and we call this version as the minimum-cost Steiner points and edges problem (MCSPE, for short). (2) If a specific material to construct all edges in such a Steiner tree has its finite length L (l ≤ L) and the cost of per piece of such a specific material used is c ₂, the objective is to minimize the total cost of the Steiner points and the pieces of such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_2+ c_2 \cdot k_3\}}$ , where T is a Steiner tree constructed, k ₂ is the number of Steiner points in T and k ₃ is the number of pieces of such a specific material used, and we call this version as the minimum-cost Steiner points and pieces of specific material problem (MCSPPSM, for short). These two variants of the Steiner tree problem are NP-hard with some applications in VLSI design, WDM optical networks and wireless communications. In this paper, we first design an approximation algorithm with performance ratio 3 for the MCSPE problem, and then present two approximation algorithms with performance ratios 4 and 3.236 for the MCSPPSM problem, respectively.     

The Steiner ratio of several discrete metric spaces

Steiner's Problem is the “Problem of shortest connectivity”, that means, given a finite set of points in a metric space (X,ρ), search for a network interconnecting these points with minimal length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. If we do not allow Steiner points, that means, we only connect certain pairs of the given points, we get a tree which is called a Minimum Spanning Tree (MST). Steiner's Problem is very hard as well in combinatorial as in computational sense, but, on the other hand, the determination of an MST is simple. Consequently, we are interested in the greatest lower bound for the ratio between the lengths of these both trees:

which is called the Steiner ratio (of (X,ρ)). We look for estimates and exact values for the Steiner ratio in several discrete metric spaces. Particularly, we determine the Steiner ratio for spaces of words, and we estimate the Steiner ratio for specific graphs.     

Class Steiner trees and VLSI-design

We consider a generalized version of the Steiner problem in graphs, motivated by the wire routing phase in physical VLSI design: given a connected, undirected distance graph with required classes of vertices and Steiner vertices, find a shortest connected subgraph containing at least one vertex of each required class. We show that this problem is NP-hard, even if there are no Steiner vertices and the graph is a tree. Moreover, the same complexity result holds if the input class Steiner graph additionally is embedded in a unit grid, if each vertex has degree at most three, and each class consists of no more than three vertices. For similar restricted versions, we prove MAX SNP-hardness and we show that there exists no polynomial-time approximation algorithm with a constant bound on the relative error, unless P = NP. We propose two efficient heuristics computing different approximate solutions in time O(¦E¦+¦V¦log¦V¦) and in time O(c(¦E¦+¦V¦log¦V¦)), respectively, where E is the set of edges in the given graph, V is the set of vertices, and c is the number of classes. We present some promising implementation results. kw]Steiner Tree; Heuristic; Approximation complexity; MAX-SNP-hardness     

On the approximation of a smooth surface with a triangulated mesh

We approximate the normals and the area of a smooth surface with the normals and the area of a triangulated mesh whose vertices belong to the smooth surface. Both approximations only depend on the triangulated mesh (which is supposed to be known), on an upper bound on the smooth surface's curvature, on an upper bound on its reach (which is linked to the local feature size) and on an upper bound on the Hausdorff distance between both surfaces.

We show in particular that the upper bound on the error of the normals is better when triangles are right-angled (even if there are small angles). We do not need every angle to be quite large. We just need each triangle of the triangulated mesh to contain at least one angle whose sinus is large enough.     

Two Heuristics for the Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each. We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

A deep-submicron steiner tree

An A-Tree is a rectilinear Steiner tree in which every sink is connected to a driver by a shortest length path, while simultaneously minimizing total wire length. This paper presents a polynomial approximation algorithm for the generalized version of an A-Tree problem with upper-bounded delays along each path from the driver to the sinks and with restrictions on the number of Steiner nodes. We refer to it as “Deep-submicron Steiner tree”, as minimizing the number of Steiner nodes is crucial for signal integrity issues in deep-submicron Very-Large-Scaled-Integrated-circuit (VLSI) designs. The idea behind the algorithm is to control two parameters in order to construct a feasible (with respect to the paths delays and the number of Steiner nodes) tree of small cost.The simulation results show the high efficiency of our approach.     

A Subdivision Approach to Maximum Parsimony

Determining an optimal phylogenetic tree using maximum parsimony, also referred to as the Steiner tree problem in phylogenetics, is NP hard. Here we provide a new formulation for this problem which leads to an analytical and linear time solution when the dimensionality (sequence length, or number of characters) is at most two. This new formulation of the problem provides a direct link between the maximum parsimony problem and the maximum compatibility problem via the intersection graph. The solution for the “two character case” has numerous practical applications in phylogenetics, some of which are discussed. Received January 16, 2006     

Rotationally optimal spanning and Steiner trees in uniform orientation metrics

We consider the problem of finding a minimum spanning and Steiner tree for a set of n points in the plane where the orientations of edge segments are restricted to λ uniformly distributed orientations, λ=2,3,4,… , and where the coordinate system can be rotated around the origin by an arbitrary angle. The most important cases with applications in VLSI design arise when λ=2 or λ=4. In the former, so-called rectilinear case, the edge segments have to be parallel to one of the coordinate axes, and in the latter, so-called octilinear case, the edge segments have to be parallel to one of the coordinate axes or to one of the lines making 45° with the coordinate axes (so-called diagonals). As the coordinate system is rotated—while the points remain stationary—the length and indeed the topology of the minimum spanning or Steiner tree changes. We suggest a straightforward polynomial-time algorithm to solve the rotational minimum spanning tree problem. We also give a simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting, and a finite time algorithm for the general Steiner tree problem with λ uniform orientations. Finally, we provide some computational results indicating the average savings for different values of n and λ both for spanning and Steiner trees.     

Approximations for node-weighted Steiner tree in unit disk graphs

Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover, NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer science, vol 5165, COCOA, 2008, pp 278–285) showed that any μ-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 μ-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy Algorithm whose approximation bound converges to 1 + ln 5 ≈ 2.61 as k → ∞, the 3-Restricted Greedy Algorithm with approximation bound 4\frac13{4\frac{1}{3}} , and the k-Restricted Variable Metric Algorithm whose approximation bound converges to 3.9334 as k → ∞.     

On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

Minimal curvature-constrained networks

This paper introduces an exact algorithm for the construction of a shortest curvature-constrained network interconnecting a given set of directed points in the plane and a gradient descent method for doing so in 3D space. Such a network will be referred to as a minimum Dubins tree, since its edges are Dubins paths (or slight variants thereof). The problem of constructing a minimum Dubins tree appears in the context of underground mining optimisation, where the objective is to construct a least-cost network of tunnels navigable by trucks with a minimum turning radius. The Dubins tree problem is similar to the Steiner tree problem, except the terminals are directed and there is a curvature constraint. We propose the minimum curvature-constrained Steiner point algorithm for determining the optimal location of the Steiner point in a 3-terminal network. We show that when two terminals are fixed and the third varied in the planar version of the problem, the Steiner point traces out a limaçon.     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

A simple proof of Hwang's theorem for rectilinear Steiner minimal trees

We present a simple, direct proof of Hwang's characterization of rectilinear Steiner minimal trees [3]: LetS be a set of at least five terminals in the plane. If no rectilinear Steiner minimal tree forS has a terminal of degree two or more, there is a tree in which at most one of the Steiner points does not lie on a straight linel, and the tree edges incident to the Steiner points onl appear on alternate sides. This theorem has been found useful in proving other results for rectilinear Steiner minimal trees.     

The steiner ratio for five points

It was conjectured by Gilbert and Pollak [5] that for any finite set of points in the Euclidean plane, the ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree is at least 3/2. The present paper proves the conjecture for five points, using a formula for the length of full Steiner trees.