Home>Results

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

[会议论文]

Improved LP-rounding Approximations for the k-Disjoint Restricted Shortest Paths Problem

Share
Edit Delete 报错

author:

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

Indexed by:

CPCI-S

Abstract:

Let G = (V, E) be a given (directed) graph in which every edge is with a cost and a delay that are nonnegative. The k-disjoint restricted shortest path (kRSP) problem is to compute k (edge) disjoint minimum cost paths between two distinct vertices s, t. is an element of V, such that the total delay of these paths are bounded by a given delay constraint D. R-0(+). This problem is known to be NP-hard, even when k = 1 [4]. Approximation algorithms with bifactor ratio (1+ 1 r, r(1+ 2(log r+ 1) r)(1+ 1/r)) and (1+ 1 r, r(1+ 2(log r+ 1) r)) have been developed for its special case when k = 2 respectively in [11] and [3]. For general k, an approximation algorithm with ratio (1, O(ln n)) has been developed for a weaker version of kRSP, the k bi-constraint path problem of computing k disjoint st-paths to satisfy the given cost constraint and delay constraint simultaneously [7]. n this paper, an approximation algorithm with bifactor ratio (2, 2) is first given for the kRSP problem. Then it is improved such that for any resulted solution, there exists a real number 0 = a = 2 that the delay and the cost of the solution is bounded, respectively, by a times and 2 - alpha times of that of an optimal solution. These two algorithms are both based on rounding a basic optimal solution of a LP formula, which is a relaxation of an integral linear programming (ILP) formula for the kRSP problem. The key observation of the two ratio proofs is to show that, the fractional edges of a basic solution to the LP formula will compose a graph in which the degree of every vertex is exactly 2. To the best of our knowledge, it is the first algorithm with a single factor polylogarithmic ratio for the kRSP problem.

Keyword:

bifactor approximation algorithm flow theory k-disjoint restricted shortest path problem LP rounding

Community:

  • [ 1 ] 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

Source :

FRONTIERS IN ALGORITHMICS, FAW 2014

ISSN: 0302-9743

Year: 2014

Volume: 8497

Page: 94-104

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

WoS CC Cited Count: 2

30 Days PV: 1

Online/Total:30/10807859
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