Approximating the k-Splittable Capacitated Network Design Problem

摘要

We consider the k-splittable capacitated network design problem (kSCND) in a graph G = (V,E) with edge weight w(e) ≥ 0, e ∈ E. We are given a vertex s ∈ V designated as a sink, a cable capacity λ ＞ 0, and a source set S (C) V with demand q(v) ≥ 0, v ∈ S. For any edge e ∈ E, we are allowed to install an integer number h(e) of copies of e. The kSCND asks to simultaneously send demand q(v) from each source v ∈ S along at most k paths to the sink s. A set of such paths can pass through a single copy of an edge in G as long as the total demand along the paths does not exceed the cable capacity λ. The objective is to find a set P of paths of G that minimizes the installing cost Σ_(e∈E)h(e) w(e). In this paper, we propose a ((k+ 1)/k + ρ_(ST))-approximation algorithm to the kSCND, where ρ_(ST) is any approximation ratio achievable for the Steiner tree problem.