Maxstatic Sink Location Problem with Capacitated Sinks

Abstract

The Maximum static flow problem, in a single-source-single-sink network, deals with finding the maximum amount of flow from a source to a sink. Given a set of possible sinks, identification of the sink that maximizes the amount of the maximum flow is an important optimization problem. In this work, we consider the problem of identification of a sink when the possible sinks have given capacities. We devise a simple network transformation so that algorithms in the uncapacitated case can be used in the capacitated one proving that the problem can be solved with strongly polynomial time complexity. Further, we propose an algorithm whose average-case complexity is better than that of an iterative procedure that iterates over all the possible sinks.