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     

Steiner Minimal Trees in Rectilinear and Octilinear Planes

This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.     

Using a Conic Formulation for Finding Steiner Minimal Trees

We present a new mathematical programming formulation for the Steiner minimal tree problem. We relax the integrality constraints on this formulation and transform the resulting problem (which is convex, but not everywhere differentiable) into a standard convex programming problem in conic form. We consider an efficient computation of an ε-optimal solution for this latter problem using an interior-point algorithm.     

欧氏空间中完备极小子流形

在一个类似于稳定不等式的条件下,得到了欧氏空间中完备极小子流形的Bernstein型定理.我们的结果部分推广了Li H.Z.和Wei G.X.的定理.     

Minimal Translation Surfaces in Euclidean Space

A translation surface in Euclidean space is a surface that is the sum of two regular curves \(\alpha \) and \(\beta \). In this paper we characterize all minimal translation surfaces. In the case that \(\alpha \) and \(\beta \) are non-planar curves, we prove that the curvature \(\kappa \) and the torsion \(\tau \) of both curves must satisfy the equation \(\kappa ^2 \tau = C\) where C is constant. We show that, up to a rigid motion and a dilation in the Euclidean space and, up to reparametrizations of the curves generating the surfaces, all minimal translation surfaces are described by two real parameters \(a,b\in \mathbb {R}\) where the surface is of the form \(\phi (s,t)=\beta _{a,b}(s)+\beta _{a,b}(t)\).     

Minimal Translation Hypersurfaces in Euclidean Space

The graph of a function f defined in some open set of the Euclidean space of dimension (p + q) is said to be a translation graph if f may be expressed as the sum of two independent functions ? and ψ defined in open sets of the Euclidean spaces of dimension p and q, respectively. We obtain a useful expression for the mean curvature of the graph of f in terms of the Laplacian, the gradient of ? and ψ as well as of the mean curvatures of their graphs. We study translation graphs having zero mean curvature, that is, minimal translation graphs, by imposing natural conditions on ? and ψ, like harmonicity, minimality and eikonality (constant norm of the gradient), giving several examples as well as characterization results.     

Uniqueness of Minimal Submanifolds in Euclidean Space

Let M be a properly immersed n-dimensional complete minimal submanifold in Euclidean space R^n+p of dimension n+p. Let A be the second fundamental form of the immersion, and r the extrinsic distance from the origin. Suppose M has one end and inf_t sup_r(x)>t r²(x) |A|²(x) < C(n,p), then M is an affine n-plane, where C(n,p) are constants given by C(n,1) = n – 1 and C(n,p) = (2/3)(n – 1) when p > 1.     

三维欧氏空间的仿射乘积曲面

定义了三维欧氏空间中的仿射乘积曲面,给出了极小仿射乘积曲面以及高斯曲率为零的仿射乘积曲面的分类,同时还给出了平均曲率为非零常数的仿射乘积曲面的分类.     

Simultaneous Packing and Covering in Three-Dimensional Euclidean Space

It is proved that the simultaneous lattice packing and latticecovering constant of every three-dimensional centrally symmetricconvex body is less than or equal to 7/4. Consequently, forany three-dimensional convex body K there is a correspondinglattice packing in which no extra translate of K can be added.     

A Plasticity Principle of Closed Hexahedra in the Three-Dimensional Euclidean Space

We prove a plasticity principle of closed hexahedra in the three dimensional Euclidean space which states that: Suppose that the closed hexahedron A ₁ A ₂?A ₅ has an interior weighted Fermat-Torricelli point A ₀ with respects to the weights B _i and let α _i0j =∠A _i A ₀ A _j . Then these 10 angles are determined completely by 7 of them and considering these five prescribed rays which meet at the weighted Fermat-Torricelli point A ₀, such that their endpoints form a closed hexahedron, a decrease on the weights that correspond to the first, third and fourth ray, causes an increase to the weights that correspond to the second and fifth ray, where the fourth endpoint is upper from the plane which is formed from the first ray and second ray and the third and fifth endpoint is under the plane which is formed from the first ray and second ray. By applying the plasticity principle of closed hexahedra to the n-inverse weighted Fermat-Torricelli problem, we derive some new evolutionary structures of closed polyhedra for n>5. Finally, we derive some evolutionary structures of pentagons in the two dimensional Euclidean space from the plasticity of weighted hexahedra as a limiting case.     

A probably fast,provably optimal algorithm for rectilinear Steiner trees

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ? > 0, there exists b > 0 such that Prob[T(n) > 2^{b√n log n]>1–?, for n log n} > 1 – ?, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.     

A heuristic for the Steiner problem in graphs

In this paper, we present a heuristic for the Steiner problem in graphs (SPG) along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.     

A Heuristic for Moment-Matching Scenario Generation

In stochastic programming models we always face the problem of how to represent the random variables. This is particularly difficult with multidimensional distributions. We present an algorithm that produces a discrete joint distribution consistent with specified values of the first four marginal moments and correlations. The joint distribution is constructed by decomposing the multivariate problem into univariate ones, and using an iterative procedure that combines simulation, Cholesky decomposition and various transformations to achieve the correct correlations without changing the marginal moments.With the algorithm, we can generate 1000 one-period scenarios for 12 random variables in 16 seconds, and for 20 random variables in 48 seconds, on a Pentium III machine.     

Almost Extrinsically Homogeneous Submanifolds of Euclidean Space

Consider a closed manifold M immersed in R^m. Suppose that the trivial bundle M × R^m = T M ⊗ ν M is equipped with an almost metric connection ~ ∇ which almost preserves the decomposition of M × R^m into the tangent and the normal bundle. Assume moreover that the difference Γ = ∂~∇ with the usual derivative ∂ in R^m is almost ~∇-parallel. Then M admits an extrinsically homogeneous immersion into R^m. Mathematics Subject Classifications (2000): 53C20, 53C24, 53C30, 53C42, 53C40.     

A Two Stage Search Heuristic for Scheduling Payments in Projects

When the Net Present Value (NPV) of a project is used as a measure of its financial performance, effective management of cash flows over the duration of the project is critical for improved profitability. Progress payments are a major component of project cash flows. In many project environments, the contractor can negotiate payment terms. Payments are typically tied to completion of project activities and therefore have significant impact on the schedule of activities and the timing of the payments. In this paper, we consider the problem of simultaneously determining the amount, timing and location of progress payments in projects to maximize NPV. Due to the combinatorial nature of the problem, heuristics are a practical approach to solving the problem. We propose a two-stage heuristic where simulated annealing is used in the first stage to determine a set of payments. In the second stage, activities are rescheduled to improve project NPV. We compare the performance of this general purpose heuristic with other problem-dependent heuristics from the literature. Our results indicate that the simulated annealing heuristic significantly outperforms the parameter-based heuristics. Although rescheduling in the second stage improves NPV, increases are relatively small in magnitude. While the specific parameters settings suggested by the simulated annealing heuristic in this study may have limited generalizability at this time due to the narrow range of problems tested, our analysis suggests that a pure simulated annealing approach is a very attractive alternative for obtaining good heuristic solutions to the complex problem of scheduling payments in projects.     

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.     

The Steiner Mapping for Three Points in Euclidean Plane

For the Euclidean plane ? the Steiner mapping associating any three points a, b, c with their median s, and the corresponding operator P _D of metric projection of the space l ₁ ³ (?) onto its diagonal subspace D = {(x,x,x): x ∈ ?}, P _D (a,b,c) = (s,s,s): s are considered. The exact value of the linearity coefficient of P _D is calculated.     

The Number of Directions Determined by Points in the Three-Dimensional Euclidean Space

   Abstract. Let X be a set of n points in the three-dimensional Euclidean space such that no three points in X are on the same line and there is no plane containing all points in X . An old conjecture states that pairs of points in X determine at least 2n-3 directions. We prove the weaker result that X determines at least 1.75n-2 directions.