Loading...
Improved approximation algorithms for computing k disjoint paths subject to two constraints
Guo, Longkun Shen, Hong Liao, Kewen
Guo, Longkun
Shen, Hong
Liao, Kewen
Citations
publications.citations-section.null.title:
Altmetric:
Author
Guo, Longkun
Shen, Hong
Liao, Kewen
Shen, Hong
Liao, Kewen
Abstract
For a given graph G with distinct vertices s and t, nonnegative integral cost and delay on edges, and positive integral bound C and D on cost and delay respectively, the k bi-constraint path (kBCP) problem is to compute k disjoint st-paths subject to C and D. This problem is known to be NP-hard, even when k=1 (Garey and Johnson, Computers and Intractability, 1979). This paper first gives a simple approximation algorithm with factor-(2,2), i.e. the algorithm computes a solution with delay and cost bounded by 2∗D and 2∗C respectively. Later, a novel improved approximation algorithm with ratio (1+β,max{2,1+ln(1/β)}) is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor-(1.369,2) approximation algorithm immediately and a factor-(1.567,1.567) algorithm by slightly modifying the algorithm. Besides, when β=0, the algorithm is shown to be with ratio (1,O(lnn)), i.e. it is an algorithm with only a single factor ratio O(lnn) on cost. To the best of our knowledge, this is the first non-trivial approximation algorithm that strictly obeys the delay constraint for the kBCP problem.
Keywords
k-disjoint bi-constraint path, NP-hard, bifactor approximation algorithm, auxiliary graph, cycle cancellation
Date
2015
Type
Journal article
Journal
Journal of Combinatorial Optimization
Book
Volume
29
Issue
1
Page Range
153-164
Article Number
ACU Department
Peter Faber Business School
Faculty of Law and Business
Faculty of Law and Business
Collections
Relation URI
Source URL
Event URL
Open Access Status
License
All rights reserved
File Access
Controlled
Notes
An error occurred retrieving the object's statistics