Abstracts
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).
Keywords:
- 2-Commodity Flow,
- Network Synthesis,
- Strongly Polynomial Algorithm
Download the article in PDF to read it.
Download