The Max Static K-Sinks Location Problem

The maximum static flow problem sends a maximum amount of flow from a set of sources to a set of sinks in a network with multiple sources and multiple sinks. Because of cost or other constraints, e.g. in evacuation planning, only a limited number of sinks may have to be chosen. To address such anissue, we consider a problem of choosing a set of at most a given number of sinks from a given set of possible sinks T as a Max Static k-sinks problem. We present a non-polynomial time algorithm to solve it and show that (T – 1)-sinks problem can be solved in a strongly polynomial time