Abstract
For a given graph G with positive integral cost and delay on edges, distinct vertices s and t, cost bound C ∈ Z + and delay bound D ∈ Z + , the k bi-constraint path (kBCP) problem is to compute k disjoint st-paths subject to C and D. This problem is known NP-hard, even when k = 1 [4]. This paper first gives a simple approximation algorithm with factor-(2,2), i.e. the algorithm computes a solution with delay and cost bounded by 2*D and 2*C respectively. Later, a novel improved approximation algorithm with ratio \((1+\beta,\,\max\{2,\,1+\ln\frac{1}{\beta}\})\) is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor-(1.369, 2) approximation algorithm by setting \(1+\ln\frac{1}{\beta}=2\) and a factor-(1.567, 1.567) algorithm by setting \(1+\beta=1+\ln\frac{1}{\beta}\). Besides, by setting β = 0, an approximation algorithm with ratio (1, O(ln n)), i.e. an algorithm with only a single factor ratio O(ln n) on cost, can be immediately obtained. To the best of our knowledge, this is the first non-trivial approximation algorithm for the kBCP problem that strictly obeys the delay constraint.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows: theory, algorithms, and applications (1993)
Bhatia, R., Kodialam, M., Lakshman, T.V.: Finding disjoint paths with related path costs. Journal of Combinatorial Optimization 12(1), 83–96 (2006)
Chao, P., Hong, S.: A new approximation algorithm for computing 2-restricted disjoint paths. IEICE Transactions on Information and Systems 90(2), 465–472 (2007)
Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman, San Francisco (1979)
Guo, L., Shen, H.: On Finding Min-Min disjoint paths. accepted by Algorithmica
Guo, L., Shen, H.: Efficient approximation algorithms for computing k disjoint minimum cost paths with delay constraint. In: IEEE PDCAT, pp. 627–631. IEEE (2012)
Guo, L., Shen, H.: On the complexity of the edge-disjoint min-min problem in planar digraphs. Theoretical Computer Science 432, 58–63 (2012)
Li, C.L., McCormick, T.S., Simich-Levi, D.: The complexity of finding two disjoint paths with min-max objective function. Discrete Applied Mathematics 26(1), 105–115 (1989)
Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Operations Research Letters 28(5), 213–219 (2001)
Orda, A., Sprintson, A.: Efficient algorithms for computing disjoint QoS paths. In: IEEE INFOCOM, vol. 1, pp. 727–738. Citeseer (2004)
Suurballe, J.W.: Disjoint paths in a network. Networks 4(2) (1974)
Suurballe, J.W., Tarjan, R.E.: A quick method for finding shortest pairs of disjoint paths. Networks 14(2) (1984)
Xu, D., Chen, Y., Xiong, Y., Qiao, C., He, X.: On the complexity of and algorithms for finding the shortest path with a disjoint counterpart. IEEE/ACM Transactions on Networking 14(1), 147–158 (2006)
Xue, G., Zhang, W., Tang, J., Thulasiraman, K.: Polynomial time approximation algorithms for multi-constrained qos routing. IEEE/ACM Transactions on Networking (TON) 16(3), 656–669 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guo, L., Shen, H., Liao, K. (2013). Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints. In: Du, DZ., Zhang, G. (eds) Computing and Combinatorics. COCOON 2013. Lecture Notes in Computer Science, vol 7936. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38768-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-38768-5_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38767-8
Online ISBN: 978-3-642-38768-5
eBook Packages: Computer ScienceComputer Science (R0)