An efficient algorithm for bicriteria minimum-cost circulation problem

This paper is concerned with a bicriteria minimum-cost circulation problem which arises in interactive multicriteria decision making. It presents a strongly polynomial algorithm for this problem, which runs in O(min{n⁶log³n,n⁴(nlogn+m)log⁵n}) time, where n and m are the numbers of vertices and edges in a graph respectively. It is achieved by making use of the parametric characterization of optimal solutions and a strongly polynomial algorithm for the single objective minimum-cost circulation problem. This idea is then extended to a minimum-cost circulation flow problem with one additional linear constraint and a strongly polynomial algorithm for this problem with the same running time is derived.