2-Commodity Integer Network Synthesis Problem

S. N. Kabadi, R. Chandrasekaran, K. P.K. Nair

Abstract


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).

Full Text:

PDF


Algorithmic Operations Research. ISSN: 1718-3235