Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows
David R. Karger, Serge A. Plotkin · 1995
Minimumcost multicommodity flow is an instance of a simpler problem (multicommodity flow)to which a cost constraint has been added.In this paper we present a general scheme for solving a large class of such "cost-added" problems-even if more than one cost is added.One of the main applications of this method is a new deterministic algorithm for approximately solving the minimumcost multicommodity flow problem.techniques in [15] and a generalization of the round-robin approach of [16] to multicommodity flow without costs.