Improved approximation algorithms for computing k disjoint paths subject to two constraints

Longkun Guo, Hong Shen, Kewen Liao

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

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 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 and a factor-(1.567, 1.567) algorithm by setting. 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.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
PublisherSpringer Berlin
Pages325-336
Number of pages12
ISBN (Print)9783642387678
DOIs
Publication statusPublished - 8 Oct 2013
Externally publishedYes
Event19th International Computing and Combinatorics Conference, COCOON 2013 - Hangzhou, China
Duration: 21 Jun 201321 Jun 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7936 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Computing and Combinatorics Conference, COCOON 2013
CountryChina
CityHangzhou
Period21/06/1321/06/13

Fingerprint Dive into the research topics of 'Improved approximation algorithms for computing k disjoint paths subject to two constraints'. Together they form a unique fingerprint.

  • Cite this

    Guo, L., Shen, H., & Liao, K. (2013). Improved approximation algorithms for computing k disjoint paths subject to two constraints. In Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings (pp. 325-336). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7936 LNCS). Springer Berlin. https://doi.org/10.1007/978-3-642-38768-5_30