Approximating Capacitated Tree-Routings in Networks

摘要

The capacitated tree-routing problem (CTR) in a graph G = (V,E) consists of an edge weight function ω : E → R~+, a sink s ∈ V, a terminal set M is contained in 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 = {Z_1, Z_2,…, Z_l} of M and a set T = {T_1, T_2,…, T_l} of trees of G such that each T_i spans Z_i ∪ {s} and satisfies ∑_(v∈Z_i)q(v) ≤ κ. 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 A; any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is ω(e). The objective is to find a solution (M,T) that minimizes the installing cost ∑_(e∈Ε)「∣{T∈T∣T contains e}|/λ」ω(e). In this paper, we propose a (2 + ρ_(ST))-approximation algorithm to the CTR, where ρ_(ST) is any approximation ratio achievable for the Steiner tree problem.