On the inapproximability of disjoint paths and minimum steiner forest with bandwidth constraints

In this paper, we study the inapproximability of several well-known optimization problems in network optimization. We show-that the max directed vertex-disjoint paths problem cannot be approximated within ratio 2^{log1-ε n} unless NP ⊆ DTIME[2^{polylog n}], the max directed edge-disjoint paths problem cannot be approximated within ratio 2^{log1-ε n} unless NP ⊆ DTIME [2^{polylog n}], the integer multicommodity flow problem in directed graphs cannot be approximated within ratio 2^{log1-ε n}unless NP ⊆ DTIME[2^{polylog n}], the max undirected vertex-disjoint paths problem does not have a polynomial time approximation scheme unless P = NP, and the minimum Steiner forest with bandwidth constraints problem cannot be approximated within ratio exp(poly(n)) unless P = NP. © 2000 Academic Press.