Indexed by:
Abstract:
Let 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∈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∈R0+. The problem is known to be NP-hard, even when k= 1 (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio (1+1r,r(1+2(logr+1)r)(1+)) and (1+1r,1+r) have been developed for 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(lnn)) 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) 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 ≤ α≤ 2 such that the weight and the length of the solution are bounded by α times and 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,lnn). © 2015, Springer Science+Business Media New York.
Keyword:
Reprint 's Address:
Email:
Source :
Journal of Combinatorial Optimization
ISSN: 1382-6905
Year: 2016
Issue: 1
Volume: 32
Page: 144-158
1 . 2 3 5
JCR@2016
0 . 9 0 0
JCR@2023
ESI HC Threshold:76
JCR Journal Grade:2
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: