Study On Approximations For Some Network Optimization Problems

As the highly developing of networks and network technique,a lot of network optimization problems are posed.Unfortunately,some of these problems are showed as NP-Complete problems.It implies that these problems can not be solved in polynomial-time. Hence,researchers focus on the approximation algorithms on these NP-Complete problems.In this thesis,we mainly study the approximation algorithms on Steiner tree problem and connected dominating set problem and their variants.These problems are classical network optimization problems and classical NP-Complete problems,even on the unit disk graphs.For all these problems,we present approximation algorithms.And then we give the theoretical analysis and obtain their approximation ratios.This thesis consists of three chapters.In Chap.1,we first introduce some basic concepts and notations of graph theory.Then some basic concepts of theory of computational complexity are introduced.Next,we present some concepts of approximation algorithm and use the vertex cover problem and a approximation algorithm of it as an example to explain some concepts.Finally,we list the main results in the thesis.Some approximation algorithms on variants of Steiner tree problem are studied in the second chapter.Given an edge-weighted graph G=(V,E) with edge-weighted function c and the terminal set X(?) V,Steiner tree problem is to find a minimum subgraph of G interconnecting X.Steiner tree problem is a classical optimization problem and NP-Complete problem.At the beginning of Chap.2,we introduce the Steiner tree problem and survey the research development.In the second section of Chap.2,we study the selected-internal Steiner tree problem,a variant of Steiner tree problem.Given an edge-weighted complete graph G=(V,E) with edge-weighted function c,and two subsets X'(?) X(?) V with |X-X'|≥2,selected-internal Steiner tree problem is to find a minimum subtree T of G interconnecting X such that any leaf of T does not belong to X'.Suppose c is metric,a(1+ρ)-approximation algorithm are presented in this section,whereρis the best-known approximation ratio for the Steiner tree problem.Given a node-weighted graph G=(V,E) with node-weighted functionω:V→R~+ and the terminal set X(?) V,node-weighted Steiner tree problem is to find a min- imum total weighted tree interconnecting all vertices in X.This problem on unit disk graphs is study in the remaining of Chap.2.In the section 3 of Chap.2,using the spanning tree method,a 5-approximation algorithm is obtained.And then,through transferring the weight from node to edge,we present another approximation algorithm with approximation ratio 2.5ρ.At the end of Chap.2,suppose the terminal set is clocal, we show that this problem has a polynomial-time approximation scheme,that is, for anyε＞0,there exists a polynomial time approximation algorithm with approximation ratio 1+ε.In Chap.3,we study the connected dominating set problem and its variants on unit disk graphs.Given a graph G,a subset C(?) V is called a connected dominating set if 1) for any vertexνεV - C,νhas a neighbor in C;2) the induced subgraph G[C] is connected.The connected dominating set problem is to find a connected dominating set of G with minimum cardinality.In the first section of Chap.3,we first introduce the background and research development of this problem.Then,the basic ideas for calculating connected dominating sets are given.In the section 2 of Chap.3,we consider the relationship of maximal independent set(MIS) and the minimum connected dominating set.Since every MIS is a dominating set and it can be constructed in polynomial-time,researchers usually find an MIS first and then connect it to computer a connected dominating set.Therefore,the ratio of the size of an MIS and the size of minimum CDS plays a key role in analyzing the approximation ratio.In this section,with the help of Voronoi diagram and Euler's formula,we improve this ratio,so that improve the approximation ratios of the all algorithms based on this method.In the section 3 of Chap.3,we study d-hop connected dominating set on unit disk graphs.Firstly,for a special case,two-hop CDS(TCDS or 2-CDS),a distributed algorithm is proposed.Then we show that the size of the output is at most 17.421opt+ 51.456,where opt is the number of nodes in an optimal 2-CDS.Final,for arbitrary integer d,we generalize the TCDS algorithm into a approximation algorithm for d-CDS with constant approximation ratio.In the forth section of Chap.3,we study the weighted connected dominating set problem on unit disk graphs,a variant of connected dominating problem.Based on the previous work and applied the PTAS algorithm of node-weighted Steiner tree problem, a(5+ε)-approximation algorithm is obtained.Next,we extend the research aspect from 2-dimension plane to 3-dimension space and study the connected dominating problem on unit ball graphs.Using greedy method,we give a approximation algorithm and show that its approximation ratio is 13+ln 10.Finally,we conclude our results and discuss the future works.