On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints

✍ Scribed by Bin Ma; Lusheng Wang

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 230 KB
• Volume: 60
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1661

✦ Synopsis

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