A New Approximation Algorithm for Computing 2-Restricted Disjoint Paths

Chao PENG; Hong SHEN

doi:10.1093/ietisy/e90-d.2.465

A New Approximation Algorithm for Computing 2-Restricted Disjoint Paths

Chao PENG, Hong SHEN

Full Text Views

0

Share
Cite this

Summary :

In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.

Publication: IEICE TRANSACTIONS on Information Vol.E90-D No.2 pp.465-472

Publication Date: 2007/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e90-d.2.465

Type of Manuscript: PAPER

Category: Algorithm Theory

Cite this

Copy

Chao PENG, Hong SHEN, "A New Approximation Algorithm for Computing 2-Restricted Disjoint Paths" in IEICE TRANSACTIONS on Information, vol. E90-D, no. 2, pp. 465-472, February 2007, doi: 10.1093/ietisy/e90-d.2.465.
Abstract: In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.2.465/_p

Copy

@ARTICLE{e90-d_2_465,
author={Chao PENG, Hong SHEN, },
journal={IEICE TRANSACTIONS on Information},
title={A New Approximation Algorithm for Computing 2-Restricted Disjoint Paths},
year={2007},
volume={E90-D},
number={2},
pages={465-472},
abstract={In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.},
keywords={},
doi={10.1093/ietisy/e90-d.2.465},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - A New Approximation Algorithm for Computing 2-Restricted Disjoint Paths
T2 - IEICE TRANSACTIONS on Information
SP - 465
EP - 472
AU - Chao PENG
AU - Hong SHEN
PY - 2007
DO - 10.1093/ietisy/e90-d.2.465
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2007
AB - In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.
ER -