A Study Of The Inverse Network Problems Under The Weighted Hamming Distance

Network optimization is one important branch of the combinatorial optimization, the goal is to find an optimal solution of the given problem. As the society advances, the inverse problems of network optimization arise. In these problems, a feasible solution is given which is not optimal under the current parameter values. And it is required to modify some parameters with minimum modification cost such that the given feasible solution forms an optimal solution. This inverse problem becomes increasingly conspicuous, attracting more and more attention from many disciplines, such as operations research, applied mathematics, computer science, management science and so on, as the computer science, the management science and the modem production technology develop. This thesis is organized into four chapters, and mainly deals with the inverse network problems under the weighted Hamming distance. In Chapter 1, we introduce some related basic concepts and knowledge. And then we discuss different models for the different problems.In Chapter 2, the inverse maximum flow problems under the weighted Hamming distance are discussed. In a given connected and directed network N(V,A,c), each arc has a specific modification cost. Let f~0 be a feasible flow of N. We are asked to modify the arc capacities such that f~0 forms a maximum flow of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we resort to the method of the minimum cut of the residual network, to produce a polynomial algorithm which runs in O(n~3) time. In the bottleneck-type model, the method of the bottleneck minimum cut of the residual network is used to present a polynomial algorithm which runs in O(m + n·log n) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~3·log m) time and O(n~3) time, respectively.In Chapter 3, we consider the following inverse min-max spanning tree problems under the weighted Hamming distance. In a given connected graph G(V. E. c), each arc has a specific modification cost. Let T~0 be a spanning tree of G. We are asked to modify the edge lengths such that T~0 forms a min-max spanning tree of G and the modification cost of modified edges is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we are first given the range of the value, and use the method of the restricted minimum weight edge cut problem to produce a polynomial algorithm which runs in O(n~4) time. In the bottleneck-type model, the method for the restricted minimum bottleneck-type weight edge cut problem is adopted to present a polynomial algorithm which runs in O(n~5) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~5) time and O(n~4) time, respectively.In Chapter 4, we consider the following inverse minimum cut problems under the weighted Hamming distance. In a given connected and directed network N(V, A, c), each arc has a specific modification cost. Let {X~0,(X|-)~0 } be an s - t cut of N. We are asked to modify the arc capacities such that {X~0, (X|-)~0 } forms a minimum cut of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Two models are studied. The first is a sum-type model, in which we show the problem is NP-hard by using the reduction from an instance of Knapsack Problem to an instance of the problem in polynomial time. In the latter bottleneck-type model, in terms of the properties of the maximum flow and minimum cut theory and the Hamming distance, we present a polynomial algorithm which runs in O(m·n~3) time.