Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}^2$$\end{document} Using Stock Pieces of Materials with Fixed LengthApproximation Algorithms for Constructing Steiner ⋯\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\cdots $$\end{document}J.-P. Li et al.

In this paper, we address the problem of constructing a Steiner tree in the Euclidean plane R2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}^2$$\end{document} using stock pieces of materials with fixed length, which is modelled as follows. Given a set X={r1,r2,⋯,rn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X=\{r_{1},r_{2},\cdots ,r_{n}\}$$\end{document} of n terminals in R2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}^2$$\end{document} and some stock pieces of materials with fixed length L, we are asked to construct a Steiner tree T interconnecting all terminals in X, and each edge in T must be constructed by a part of that stock piece of material. The objective is to minimize the cost of constructing such a Steiner tree T, where the cost includes three components, (1) The cost of Steiner points needed in T; (2) The construction cost of constructing all edges in T and (3) The cost of stock pieces of such materials used to construct all edges in T. We can obtain two main results. (1) Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem, we present a simple 4-approximation algorithm in time O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} to solve this new problem; (2) Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the bin-packing problem, we design a 3-approximation algorithm in time O(n3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{3})$$\end{document} to resolve this new problem.