## A combinatorial arc tolerance analysis for network flow problems.(English)Zbl 1213.90075

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.

### MSC:

 90B10 Deterministic network models in operations research 90C35 Programming involving graphs or networks
Full Text: