• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Guo, Longkun (Guo, Longkun.) [1]

Indexed by:

EI

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:

Approximation algorithms Budget control Computation theory Constraint satisfaction problems Directed graphs

Community:

  • [ 1 ] [Guo, Longkun]College of Mathematics and Computer Science, Fuzhou University, Fuzhou, China

Reprint 's Address:

  • [guo, longkun]college of mathematics and computer science, fuzhou university, fuzhou, china

Show more details

Related Keywords:

Related Article:

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:

WoS CC 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:

Online/Total:145/10279864
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1