TY - JOUR
T1 - On the inapproximability of disjoint paths and minimum steiner forest with bandwidth constraints
AU - Ma, Bin
AU - Wang, Lusheng
PY - 2000
Y1 - 2000
N2 - 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-ε nunless 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. © 2000 Academic Press.
AB - 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-ε nunless 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. © 2000 Academic Press.
UR - http://www.scopus.com/inward/record.url?scp=0037761744&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0037761744&origin=recordpage
U2 - 10.1006/jcss.1999.1661
DO - 10.1006/jcss.1999.1661
M3 - RGC 21 - Publication in refereed journal
VL - 60
SP - 1
EP - 12
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
IS - 1
ER -