The Constrained Routing And Network Construction Problems

The Chinese postman problem is one of important routing problems. We study a further generalization of the Chinese postman problem that is called as the con-strained arc routing problem in mixed graphs, and we also consider two versions of this generalization problem specialized to graphs and digraphs, i.e., the constrained edge routing problem in graphs and the constrained arc routing problem in digraphs, we design an approximation algorithm and two polynomial-time exact algorithms to solve them, respectively. We consider the maximum Hamiltonian path problem with7-triangle inequality property, and present two randomized approximation al-gorithms and an approximation algorithm to solve it. We also study two subgraph construction problems, i.e., the restricted shortest path construction problem and the subgraph construction problem with rational objective function, and give two approximation algorithms to solve them, respectively. Finally, we consider four op-timization versions of the3-partitioning problem, and provide four polynomial-time approximation schemes to solve them, respectively.This dissertation is divided into seven chapters:Chapter1introduces some research backgrounds, motivations and our main results.In Chapter2, we present some basic concepts, some related optimization prob-lems and algorithms.In Chapter3, we study the constrained arc routing problem in mixed graphs, and we design a (1+l/l0)-approximation algorithm in O(n2m3logn) time to solve it by using network flow techniques, where l0=min{l(e)|e∈E}. For the constrained edge routing problem in graphs, we present an optimal combinatorial algorithm in time O(n3) to solve it, and for the constrained arc routing problem in digraphs, we present an optimal combinatorial algorithm in time O(nm2logn) to solve it.In Chapter4, we consider the maximum Hamiltonian path problem with γ-triangle inequality property (MHP, for short). We present two randomized approxi-mation algorithms to solve it, whose expected performance ratios are (4γ+1)/6γ- 1/2nγ and (3γ+l/2)/4γ-O(1/), respectively. We also design an approxima-tion algorithm with performance ratio (4-y+1)/6γ to solve the MHP problem with a specified endpoint.In Chapter5, we consider the restricted shortest path construction problem, and we design an asymptotic approximation algorithm in time0(mn(log logn+1/e)) to solve it, satisfying OUT<7(1+e)OPT/4+co/2for any ε>0. For the special version of this problem, where c(e)=0holds for each arc e∈A, we present an asymptotic approximation algorithm in time O(n2) to solve it, satisfying OUT<3OPT/2+(ko+1)/4, where ko denotes the minimum number of arcs with relative length L/2<Wf(e)<2L/3in a shortest path P among all shortest paths from s to t in the digraph D.In Chapter6, we study the subgraph construction problems with rational ob-jective function. It is an extension of the minimization ratio problem Q in dou-bly edge-weighted graphs, where the objective of the problem Q is to choose a minimization-ratio subset of edges, such that the edges chosen form a particular subgraph. In the extension Q, these edges are further required to be cut from some stock pieces of length L, such that the objective is to minimize the cost-to-length ratio. When the minimization ratio problem Q is solved by a polynomial-time ex-act algorithm, we design an almost polynomial-time exact algorithm to solve the extension Q’, which achieves a cost-to-length ratio that is guaranteed to exceed the optimum at most co/L. When the minimization ratio problem Q is N P-hard and can be α-approximated, we present an asymptotic α-approximation algorithm to solve the extension Q’, satisfying OUT≤α· OPT+co/L. When Q is the minimum ratio path problem, we prove that the extension Q’ as well as the problem Q can not be approximated within performance ratio/(n), where f(n) is any polynomial-time computable function.In Chapter7, we study four optimization versions of the3-partitioning problem, and we present four polynomial-time approximation schemes for these four problems, respectively.In the end of this dissertation, we provide some conclusions and propose some problems that would be studied in future.