The Design Of Algorithms And Analyses Of Three Optimization Problems

In this dissertation,we consider three optimization problems:the con-strained rural postman problem on mixed graphs,the constrained arbores-cence augmentation problem and the capacitated network construction prob-lem.The constrained rural postman problem on mixed graphs and the ca-pacitated network construction problem generalize the constrained Chinese postman problem on mixed graphs and the network construction problem,respectively.The constrained arborescence augmentation problem is a new variant of the augmentation problem.Research on these optimization prob-lems has theoretical values and practical significances.This dissertation is divided into six following chapters:In Chapter 1,we introduce the background of the NP-complete prob-lems,the research status of the arc routing problem,the augmentation prob-lem and the network construction problem,and then we state main results that we have obtained in this dissertation.In Chapter 2,we introduce the basic concepts of graph theory,combinatorial optimization and design of approximation algorithms.In Chapter 3,we consider the constrained rural postman problem on mixed graphs(CRPM),that is definecd as follows.For any weighted mixed G=(V,E?A;w),where a length function w:E?A?Q+,and two required subsets E'(?)E and A' C A,two integer functions l,u:E' U A'?f Z+,satisfying l(e)?(e)for(?)e?E'?A',we are asked to determine a minimum length tour C traversing each edge e? E'?A' at least l(e)and at most u(e)times.And we obtain some following results.(1)For the CRPM problem where A'?? and A'?A,we prove that it is NP-hard to determine a feasible tour.(2)For the CRPM problem where A' ? A,we show first that it is NP-hard to determine a feasible tour for this problem for the case where each required edge e ? E' satisfies 1(e)= u(e);we secondly design a 3-approximation algorithm to solve the CRPM where each required edge e ?E' satisfies 1(e)<u(e)we thirdly consider the constrained stacker crane problem and design a 9/5-approximation algorithm to solve it.(3)For the CRPM problem where A' =(?),we prove that it is NP-hard to determine a feasible tour for the CRPM problem for the case where each required edge e E E' satisfies l(e)= 1 and u(e)= k,and then we provide a(? + 2)-approximation algorithm to solve this problem where each required edge e ?E' satisfies u(e)=?,where p is the performance ratio of approxi-mation algorithm to solve the asymmetric traveling salesman problem.(4)We consider the constrained rural postman problem on graphs.We design a 3-approximation algorithm to solve this problem,and in addition,we present a 3/2-approximation algorithm to solve this problem for the case where each required edge e E E' satisfies 1(e)<u(e).In Chapter 4,we consider the constrained arborescence augmentation problem.For the case where the root is fixed at a vertex r,we design an optimal combinatorial algorithm.For the case where the root is not fixed at a vertex r,we prove that it cannot be approximated within per-formance ratio(0.72 · ln(log2n-2)),unless P?NP,and we then design an(i(i-1)k1/i)parameterized algorithm in O(kinim + kini?1logn)to solve this problem,where i>0.In addition,when we choose i = logk,the per-formance ratio of this parameterized algorithm is O(log2k)and the running time is O(nlogkm + nlogk?1 logn).For the case where each arc e? A satisfies w(e)= 1,we design an optimal combinatorial algorithm.In Chapter 5,we consider the capacitated network construction problem(CNC).For the CNC problem,we design an asymptotic 7/2-approximation algorithms.For the CNC problem where w(ei)?w(ej)implies c(ei)?c(ej)for two function w(·)and c(·),we present an asymptotic 13/4-approximation algorithms.For the CNC problem where each edge e ?E satisfies c(e)= 0,we design an asymptotic 3-approximation algorithm.In Chapter 6,we give some conclusions in this dissertation and then propose some problems which will be considered in future.