𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A tight lower bound for the Steiner ratio in Minkowski planes

✍ Scribed by Biao Gao; Ding-Zhu Du; Ronald L. Graham

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
804 KB
Volume
142
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A minimum Steiner tree for a given set X of points is a network interconnecting the points of X having minimum possible total length. The Steiner ratio for a metric space is the largest lower bound for the ratio of lengths between a minimum Steiner tree and a minimum spanning tree on the same set of points in the metric space. In this note, we show that for any Minkowski plane, the Steiner ratio is at least 2/3. This settles a conjecture of Cieslik (1990) and also Du et al. (1991).

πŸ“œ SIMILAR VOLUMES

A strong lower bound for the Node Weight
A strong lower bound for the Node Weighted Steiner Tree Problem
✍ Engevall, Stefan; GοΏ½the-Lundgren, Maud; VοΏ½rbrand, Peter πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 84 KB πŸ‘ 1 views

In this paper, we study the Node Weighted Steiner Tree Problem (NSP). This problem is a generalization of the Steiner tree problem in the sense that vertex weights are considered. Given an undirected graph, the problem is to find a tree that spans a subset of the vertices and is such that the total

A Lower Bound for the Height in Abelian
A Lower Bound for the Height in Abelian Extensions
✍ Francesco Amoroso; Roberto Dvornicich πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 172 KB

We produce an absolute lower bound for the height of the algebraic numbers (different from zero and from the roots of unity) lying in an abelian extension of the rationals. The proof rests on elementary congruences in cyclotomic fields and on Kronecker Weber theorem.

A Sharp Lower Bound in the Distortion Th
A Sharp Lower Bound in the Distortion Theorem for the Sakaguchi Class
✍ I.R. Nezhmetdinov πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 61 KB

A sharp lower bound is obtained for f Ј z in the class SSP of functions starlike with respect to symmetric points. As a consequence, some results are improved both for SSP and the class of uniformly starlike functions.