A combinatorial arc tolerance analysis for network flow problems (Q930771)

Summary: For the separable convex cost flow problem, we consider the problem of determining a tolerance set for each arc cost function. For a given optimal flow \(x\), a valid perturbation of \(c_{ij}(x)\) is a convex function that can be substituted for \(c_{ij}(x)\) in the total cost function without violating the optimality of \(x\). Tolerance set for an \(\text{arc}(i,j)\) is the collection of all valid perturbations of \(c_{ij}(x)\). We characterize the tolerance set for each \(\text{arc}(i,j)\) in terms of nonsingleton shortest distances between nodes \(i\) and \(j\). We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes in \(O(n^3)\) time where \(n\) denotes the number of nodes in the given graph.