Approximation Algorithms For Solving Some Constrained Steiner Tree Problems In The Plane R~2

Network design problem is one of the most important problems in combinatorial optimization.It is of important theoretical and practical significance to study this topic.In this dissertation,we consider four constrained Steiner tree problems in the plane R2,i.e.,(1)the line-capacitated minimum Steiner tree problem,(2)the minimum number of Steiner points of line-constrained Steiner tree problem,(3)the problem of full Steiner trees with minimum number of Steiner points in the Euclidean plane R2,and(4)the minimum rectilinear Steiner tree problem with bounded edge-length.The former two problems are two variations of the classic minimum Steiner tree in the Euclidean plane,where one "free" straight line l∈R2 can be added to the feasible solution,and the latter two problems are two variations of the minimum number of Steiner points in the plane R2,where the length of each edge in a Steiner tree considered does not exceed a given constant L>0.We design some approximation algorithms in polynomial time to solve these four problems.In addition,we present some algorithms to solve special versions of these four problems.This dissertation is divided into the following six chapters.In Chapter 1,we present the backgrounds,our new problems and the main results obtained.In Chapter 2,we provide some basic concepts of graph theory and combinatorial optimization,some related optimization problems and related results.In Chapter 3,we address the line-capacitated minimum Steiner tree problem(LcMStT,for short),and then obtain the following three main results.(1)Given a ρ1Ly-approximation algorithm A1Lf to solve the 1-line-fixed minimum Steiner tree problem(1Lf-MStT,for short),we design a(2ρ1Lf+2)-approximation algorithm in time O(n2g(n))to solve the Lc-MStT problem,where n is the number of terminals,and O(g(n))is the time complexity of the algorithm A1Lf.(2)Given a ρst-approximation algorithm Ast to solve the Euclidean minimum Steiner tree problem and a ρ1Lf-approximation algorithm A1Lf to solve the 1Lf-MStT problem,respectively,we present a(ρstρ1Lf+2)-approximation algorithm in time O(n2(f(n)+g(n)))to solve the Lc-MStT problem,where n is the number of terminals,O(f(n))and O(g(n))are the time complexity of the algorithms Ast and A1Lf,respectively.(3)When demand of each terminal r∈X is less than C/2,using a ρ1Lf-approximation algorithm A1Lf to solve the 1Lf-MStT problem,we provide a(ρ1Lf+2)-approximation algorithm in time O(n2g(n))to resolve the Lc-MStT problem,where n is the number of terminals and O(g(n))is the time complexity of the algorithm A1Lf;When demand ofeach terminal r∈X is at least C/2,we present an exact algorithm in time O(n5)to resolve the Lc-MStT problem,where n is the number of terminals.In Chapter 4,we consider the problem of minimum number of Steiner points of lineconstrained Steiner tree(MNSP-LcMStT,for short),and then obtain the following two main results.(1)We design an asymptotic 4-approximation algorithm in time O(n4 log n)to solve the MNSP-LcMStT problem,where n is the number of terminals.(2)For a special version of the MNSP-LcMStT problem,where the weight of the line-constrained Steiner tree is minimized,we provide a 2-approximation algorithm intime O(n3 log n log β(n)),where n is the number of terminals and β(n)=min{i|log(i)n≤4-6/n}.In Chapter 5,we consider the problem of full Steiner trees with minimum number of Steiner points in the Euclidean plane R2(FStT-MNSP,for short),and then obtain the following two main results.(1)Given an α-approximation algorithm Aa to solve the unit disk cover problem in the Euclidean plane R2,we construct a 4(α+1)-approximation algorithm in time O(h(n)+n log n)to solve the FStT-MNSP problem,where n is the number of terminals and O(h(n))is the time complexity of the algorithm Aa.(2)Using the combination of the algorithm designed in(1)and a 4-approximation algorithm to solve the unit disk cover problem in the Euclidean plane R2,we give a 13approximation algorithm in time O(n log n)to resolve the FStT-MNSP problem,where n is the number of terminals.In Chapter 6,we address the minimum rectilinear Steiner tree problem with bounded edge-length(RMStT-BEL,for short),and then obtain the two main results.(1)Using techniques of constructing a minimum rectilinear spanning tree on X and solving the bin-packing problem,we design a 3-approximation algorithm in time O(n log n)to solve the RMStT-BEL problem,where n is the number of terminals;(2)Using the combination of the algorithm designed in(1)and a greedy strategy,we present a 2-approximation algorithm in time O(n3)to solve a special version of this problem,where n is the number of terminals.At the end of the dissertation,we present our conclusions and provide some new problems that may be considered in future.