TY - JOUR AU - S. N. Kabadi AU - R. Chandrasekaran AU - K. P.K. Nair PY - 1969/12/31 Y2 - 2019/10/18 TI - 2-Commodity Integer Network Synthesis Problem JF - Algorithmic Operations Research JA - AOR VL - 4 IS - 2 SE - Articles DO - UR - https://journals.lib.unb.ca/index.php/AOR/article/view/12477 AB - We consider the following 2-commodity, integer network synthesis problem: Given two n×n, non-negative, symmetric, integer-valued matrices R = (rij) and S = (sij) of minimum flow requirements of 2 different commodities, construct an undirected network G = [N, E, c] on node set N = {1, 2, . . . , n} with integer edge capacities {c(e) : e ∈ E}, such that: (i) for any two pairs (i, j) and (k, l), i ≠ j, k ≠ l, of nodes in N, we can simultaneously send rij units of flow of commodity 1 from i to j and skl units of flow of commodity 2 from k to l in G; and (ii) z = Σ {c(e) : e ∈ E} is minimum. We present strongly polynomial, combinatorial algorithms for certain special cases of the problem; and for the general problem, we present a strongly polynomial, combinatorial algorithm that produces a feasible solution with objective function value no more than (the optimal objective function value +3). ER -