| We abstract a lot of complicated problems in our reality life into combinations of classic optimization problems basing on the insightful understanding and analyses of these problems.Mathematical models are well constructed by using requirements of academic researches,our reality life and industrial activities as objectives.It has brought us new opportunities and challenges how to solve these optimization problems.In this dissertation,we address the problem Q’ of constructing the required subgraphs using stock pieces of fixed length,which is different from the minimumcost edge-weighted subgraph problem Q,and meanwhile the problem Q’ is treated as a generalization of the problem Q.Given an α-approximation algorithm to solve the problem Q,we design a 2α-approximation algorithm and another asymptotic（7α/4）-approximation algorithm to solve the problem Q’.In addition,we provide two 3/2approximation algorithms and two fully asymptotic polynomial-time approximations schemes（abbreviated as AFPTAS）to solve two special versions of the problem Q’,respectively.We consider the 1-line minimum rectilinear Steiner tree problem,which is treated as a generalization of the minimum rectilinear Steiner tree problem.We present an exact algorithm in time O（n log n）to solve the constrained minimum rectilinear Steiner tree problem,and then show that the same algorithm mentioned-above is a 1.5-approximation algorithm to solve the 1-line-fixed minimum rectilinear Steiner tree problem.Using a combination of the algorithm mentioned-above for many times and an important Lemma 4.9 proved by using some techniques of computational geometry,we provide a 1.5-approximation algorithm in time O（n3 log n）to solve the 1-line minimum rectilinear Steiner tree problem,and we also present another approximation algorithm to solve a special version of the problem.Inspired by applications of the diameter-constrained minimum spanning tree problem in communication networks,where it is more efficient to transmit information,we propose the diameter-constrained minimum shortest paths tree problem and its related problems.We design an exact algorithm in time O（n3）to solve the radius-constrained minimum shortest paths tree problem,and present an exact algorithm in time O（mn2+n3 log n）to solve a special version of the diameter-constrained minimum shortest paths tree problem. |
