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

author:

Guo, Longkun (Guo, Longkun.) [1] (Scholars:郭龙坤)

Indexed by:

CPCI-S EI Scopus SCIE

Abstract:

Let 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 , 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 . The problem is known to be -hard, even when (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio and have been developed for 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 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 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 such that the weight and the length of the solution are bounded by times and 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 .

Keyword:

Bifactor approximation algorithm Cycle cancellation Flow theory k-Disjoint constrained shortest path LP rounding

Community:

  • [ 1 ] [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Peoples R China

Reprint 's Address:

  • 郭龙坤

    [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Peoples R 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 Discipline: MATHEMATICS;

ESI HC Threshold:76

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 9

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:662/10278665
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