Paper Info
Title
Efficient Approximation Algorithms for Computing \emph{k} Disjoint Restricted Shortest Paths.
Abstract
Network applications, such as multimedia streaming and video conferencing, impose growing requirements over Quality of Service (QoS), including bandwidth, delay, jitter, etc. Meanwhile, networks are expected to be load-balanced, energy-efficient, and resilient to some degree of failures. It is observed that the above requirements could be better met with multiple disjoint QoS paths than a single one. Let $G=(V,\, E)$ be a digraph with nonnegative integral cost and delay on every edge, $s,\, t\in V$ be two specified vertices, and $D\in\mathbb{Z}_{0}^{+}$ be a delay bound (or some other constraint), the \emph{$k$ Disjoint Restricted Shortest Path} ($k$\emph{RSP})\emph{ Problem} is computing $k$ disjoint paths between $s$ and $t$ with total cost minimized and total delay bounded by $D$. Few efficient algorithms have been developed because of the hardness of the problem. In this paper, we propose efficient algorithms with provable performance guarantees for the $k$RSP problem. We first present a pseudo-polynomial-time approximation algorithm with a bifactor approximation ratio of $(1,\,2)$, then improve the algorithm to polynomial time with a bifactor ratio of $(1+\epsilon,\,2+\epsilon)$ for any fixed $\epsilon>0$, which is better than the current best approximation ratio $(O(1+\gamma),\, O(1+\frac{1}{\gamma})\})$ for any fixed $\gamma>0$ \cite{orda2004efficient}. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys the constraint for the $k$RSP problem.
Year
Venue
Field
2015
CoRR
Discrete mathematics,Approximation algorithm,Combinatorics,Disjoint sets,Vertex (geometry),Shortest path problem,Jitter,Time complexity,Digraph,Mathematics,Bounded function
DocType
Volume
Citations 
Journal
abs/1504.05519
0
PageRank 
References 
Authors
0.34
12
4
Name
Order
Citations
PageRank
Longkun Guo165.49
Kewen Liao25111.16
Hong Shen349952.98
Peng Li420718.60