Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows
Minimum cost 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. Our algorithm finds a (1 + e) approximation to the minimum cost flow in 0(e-3kmn) time, where k is the number of commodities, m is the number of edges, and n is the number vertices in the input problem. This improves the previous best deterministic bounds of O(e-4kmn2 ) [9] and 6(e-2k2m2) [15] by f~ctors of n/6 and ekm/n respectively. In fact, it even dominates the best randomized bound of 0(e-2km2) [15]. The algorithm presented in this paper efficiently solves several other interesting generalizations of rein-cost flow problems, such as one in which each commodity can have its own distinct shipping cost per edge, or one in which there is more than one cost measure on the flows and all costs must be kept small simultaneously. Our approach is based on an extension of the approximate packing techniques in [15] and a generalization of the round-robin approach of [16] to multicommodity flow without costs.