Minimum cost flow in a network with an underestimated arc capacity

Abstract

There are a lot of real-world problems that can be modeled and solved as minimum cost flow problems. Sometimes in this problem, minor changes may occur as, for instance, the capacity of an arc may vary over time. In this paper we study the case in which the capacity of a given arc is augmented by a given value a. Supposing that a minimum cost flow has been already established in a network G, we focus on the problem of finding a minimum cost flow in a network having the same structure as G and the same arc costs and capacities excepting one: the capacity of a given arc (k, l) which has been increased by units. We describe a method for obtaining a minimum cost flow in the modified network in O(am) time starting from the minimum cost flow in the original network.