Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/83728
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Improved approximation algorithms for computing k disjoint paths subject to two constraints |
Author: | Guo, L. Shen, H. Liao, K. |
Citation: | Proceedings of the 19th International Computing and Combinatorics Conference, COCOON 2013, 2013, Hangzhou, China, June 21-23, 2013 / D.-Z. Du, G. Zhang (eds.), pp.325-336 |
Publisher: | Springer |
Publisher Place: | Germany |
Issue Date: | 2013 |
Series/Report no.: | Lecture Notes in Computer Science |
ISBN: | 9783642387678 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Computing and Combinatorics Conference (19th : 2013 : Hangzhou) |
Statement of Responsibility: | Longkun Guo, Hong Shen, and Kewen Liao |
Abstract: | For a given graph G with positive integral cost and delay on edges, distinct vertices s and t, cost bound C ∈ Z + and delay bound D ∈ Z + , the k bi-constraint path (kBCP) problem is to compute k disjoint st-paths subject to C and D. This problem is known NP-hard, even when k = 1 [4]. 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+ln1β}) 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 by setting 1+ln1β=2 and a factor-(1.567, 1.567) algorithm by setting 1+β=1+ln1β . Besides, by setting β = 0, an approximation algorithm with ratio (1, O(ln n)), i.e. an algorithm with only a single factor ratio O(ln n) on cost, can be immediately obtained. To the best of our knowledge, this is the first non-trivial approximation algorithm for the kBCP problem that strictly obeys the delay constraint. |
Keywords: | k-disjoint bi-constraint path NP-hard bifactor approximation algorithm auxiliary graph cycle cancellation |
Rights: | © Springer-Verlag Berlin Heidelberg 2013 |
DOI: | 10.1007/978-3-642-38768-5_30 |
Published version: | http://dx.doi.org/10.1007/978-3-642-38768-5_30 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_83728.pdf Restricted Access | Restricted Access | 343.4 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.