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 2log1−ε n unless NP⊆DTIME[2polylog n], the max directed edge-disjoint paths problem cannot be approximated within ratio 2log1−ε n unless NP⊆DTIME[2polylog n], the integer multicommodity flow problem in directed graphs cannot be approximated within ratio 2log1−ε n unless NP⊆DTIME[2polylog 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.