Approximating Capacitated Tree-Routings in Networks

摘要

The capacitated tree-routing problem (CTR) in a graph G = (V,E) consists of an edge weight function w:E→R+, a sink s ∈ V, a terminal set M C V with a demand function q:M→R~+, a routing capacity κ> 0, and an integer edge capacity λ ≥ 1. The CTR asks to find a partition M = {Z1, Z2, ..., Ze} of M and a set T = {T1, T2, ...,Te} of of G such that each Ti spans Zi ∪ {s} and satisfies ∑v∈Z, q(v) ≤ k. A subset of trees in T can pass through a single copy of an edge e ∈E as long as the number of these trees does not exceed the edge capacity λ; any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution (M, T) that minimizes the installing cost ∑v∈E「|{T ∈T| T contains e}|」w(e). In this paper, we propose a (2 + ρst)-approximation algorithm to the CTR, where is any approximation ratio achievable for the Steiner tree problem.