Indexed by:
Abstract:
Let G = (V, E) be a given graph, S subset of V be a terminal set, r is an element of S be the selected root. Assume that c : E -> R+ and d : E -> R+ are cost and delay functions on the edges respectively. The shallow-light Steiner tree (SLST) problem is to compute a minimum cost tree spanning all the terminals of 5, such that the delay between r and every other terminal is bounded by a given delay constraint D is an element of R-0(+). Since in real network, the cost and delay of a link are always related, this paper addresses two such special cases: the constrained Steiner tree (CST) problem, a special case of the SLST problem that c(e) = sigma d(e) for every edge, and the constrained spanning tree (CPT) problem, a further special case of the CST problem when S = V. This paper first shows that even when c(e) = d(c), the CPT problem is NP-hard, and admits no (1 + epsilon, gamma ln (vertical bar V vertical bar) approximation algorithm algorithm for some fixed gamma > 0 and any epsilon < 1/vertical bar V vertical bar+vertical bar E vertical bar+1 The inapproximability result can be applied to the CST problem immediately. Based on the above observation of the hardness to develop a single factor approximation algorithm, we give an approximation algorithm with a bifactor ratio of (rho, 1.39 + 2.78/rho - 1) for the CST problem, where 1.39 is the best approximation ratio for the minimum Steiner tree problem in the current state of the art. As a consequence, for the applications where cost and delay are of equal importance, an approximation with bifactor (2.87, 2.87) for CST can be immediately obtained by setting rho = 1.39 + 2.78/rho - 1. This indicates that the SLST problem admits approximation algorithms with constant bifactor ratio, when the cost and delay are linearly dependent.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
2014 SIXTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND PROGRAMMING (PAAP)
ISSN: 2168-3034
Year: 2014
Page: 99-103
Language: English
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: