| Network optimization and improvement problem is an important researchdirection in the field of graph theory and combinatorial optimization. Manyapplications of these problems have been found in the real world. Networkoptimization problem is to find an optimal solution of the problem under someconstraints, while network improvement problem is also called the reverse problemof network optimization problem, it is to modify the parameters of an optimizationproblem, such that under the new parameters, the network can satisfy some certaindesires or constraints of the problem and the total modification cost is minimum. Inthis paper, we consider the k-supplierproblem, the telecommunication networkimprovement problem under l norm and the partial minimum connected spanningsubgraph improvement problem with given cycle rank. The details are as follows:Firstly, we study the k-supplierproblem, and we present a greedy-type3-approximation algorithm. k-supplierproblem is an NP-hard problem and the bestapproximation ratio is proved to be3. In this paper, we use greedy technique, fromthe view of the clients, to choose the nearest supplier. By the iterative modifications,we obtain the polynomial time3-approximation greedy algorithm. And we present aninstance to show the efficiency of the algorithm. The algorithm is easy to imply, runsfast, and has high accuracy.Secondly, we study a kind of telecommunication network improvementproblem under l norm. This problem has some application background. In thispaper, we consider a kind of telecommunication network optimization problem. Bythe definition of weakly dominant set, we present anO(V2)polynomial timealgorithm based on the algorithm of the minimum spanning tree. And we obtain themodel of its improvement problem. Finally, we propose anO(V2(log E V))polynomial time algorithm for the improvement problem by using a Newton-typemethod.Thirdly, we consider the partial minimum connected spanning subgraphimprovement problem with given cycle rank. For the case that the given subgraph is a connected subgraph with cycle rank k, we contract the given subgraph and obtaina minimum spanning tree. Then we expand the given subgraph, finally we design apolynomial time algorithm for the partial improvement problem. When the givensubgraph is a spanning tree, by gradually reducing the edge weight of the givensubgraph, we construct a connected spanning subgraph with cycle rank k containingthe given subgraph. And we show that this connected subgraph is the minimum one.Then we design a polynomial time algorithm for solving this kind of partialimprovement problem. |
