Minimum cost flow in a network with an overestimated arc capacity

Abstract

There are many situations in which minimum cost flows are solutions to real-world problems. Sometimes, in these problems, minor data changes may occur and these will lead to corresponding changes in the networks, in which the practical problems are modeled as minimum cost ow problems. For instance, the capacity of an arc may increase or decrease in time. In this paper, the case in which the capacity of a given arc decreases by a given value is studied. We focus on the problem of finding a minimum cost flow in a network that differs from the initial network G, in which a mini-mum cost flow has been already determined, only by the capacity of a given arc (k, l) which has been decreased by a units. We develop an algorithm for establishing a minimum cost ow in the modified network in O(anm) time, starting from the minimum cost flow in the original network.