Efficient approximation algorithms for computing k disjoint constrained shortest paths

Longkun Guo ()
Additional contact information
Longkun Guo: Fuzhou University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 9, 144-158

Abstract: Abstract Let $$G=(V,\, E)$$ G = ( V , E ) be a given directed graph in which every edge e is associated with two nonnegative costs: a weight w(e) and a length l(e). For a pair of specified distinct vertices $$s,\, t\in V$$ s , t ∈ V , the k-(edge) disjoint constrained shortest path (kCSP) problem is to compute k (edge) disjoint paths between s and t, such that the total length of the paths is minimized and the weight is bounded by a given weight budget $$W\in \mathbb {R}_{0}^{+}$$ W ∈ R 0 + . The problem is known to be $${\mathcal {NP}}$$ NP -hard, even when $$k=1$$ k = 1 (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio $$\left( 1\,+\,\frac{1}{r},\, r\left( 1\,+\,\frac{2(\log r\,+\,1)}{r}\right) (1\,+\,\epsilon )\right) $$ 1 + 1 r , r 1 + 2 ( log r + 1 ) r ( 1 + ϵ ) and $$(1\,+\,\frac{1}{r},\,1\,+\,r)$$ ( 1 + 1 r , 1 + r ) have been developed for $$k=2$$ k = 2 in Orda and Sprintson (IEEE INFOCOM, pp. 727–738, 2004) and Chao and Hong (IEICE Trans Inf Syst 90(2):465–472, 2007), respectively. For general k, an approximation algorithm with ratio $$(1,\, O(\ln n))$$ ( 1 , O ( ln n ) ) has been developed for a weaker version of kCSP, the k bi-constraint path problem which is to compute k disjoint st-paths satisfying a given length constraint and a weight constraint simultaneously (Guo et al. in COCOON, pp. 325–336, 2013). This paper first gives an approximation algorithm with bifactor ratio $$(2,\,2)$$ ( 2 , 2 ) for kCSP using the LP-rounding technique. The algorithm is then improved by adopting a more sophisticated method to round edges. It is shown that for any solution output by the improved algorithm, there exists a real number $$0\le \alpha \le 2$$ 0 ≤ α ≤ 2 such that the weight and the length of the solution are bounded by $$\alpha $$ α times and $$2-\alpha $$ 2 - α times of that of an optimum solution, respectively. The key observation of the ratio proof is to show that the fractional edges, in a basic solution against the proposed linear relaxation of kCSP, exactly compose a graph in which the degree of every vertex is exactly two. At last, by a novel enhancement of the technique in Guo et al. (COCOON, pp. 325–336, 2013), the approximation ratio is further improved to $$(1,\,\ln n)$$ ( 1 , ln n ) .

Keywords: LP rounding; Flow theory; k-Disjoint constrained shortest path; Bifactor approximation algorithm; Cycle cancellation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9934-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:1:d:10.1007_s10878-015-9934-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9934-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().