A combinatorial arc tolerance analysis for network flow problems

摘要

For the separable convex cost flow problem, we consider the problem of determining tolerance set for each arc cost function. For a given optimal flowx, a valid perturbation ofcij(x)is a convex function that can be substituted forcij(x)in the total cost function without violating the optimality ofx. Tolerance set for anarc(i,j)is the collection of all valid perturbations ofcij(x). We characterize the tolerance set for eacharc(i,j)in terms of nonsingleton shortest distances between nodesiandj. We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes inO(n3)time wherendenotes the number of nodes in the given graph.