A combinatorial arc tolerance analysis for network flow problems. Issue 2 (25th July 2005) - Sokkalingam, P. T.; Sharma, Prabha
Abstract : 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 ofc i j ( x ) is a convex function that can be substituted forc i j ( x ) in the total cost function without violating the optimality ofx . Tolerance set for ana r c ( i, j ) is the collection of all valid perturbations ofc i j ( x ) . We characterize the tolerance set for eacha r c ( i, j ) in terms of nonsingleton shortest distances between nodesi andj . We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes inO ( n 3 ) time wheren denotes the number of nodes in the given graph.