کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128283 | 1378587 | 2016 | 13 صفحه PDF | دانلود رایگان |
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 tâV designated as a sink, a cable capacity λ>0, and a source set SâV with demand d(v)â¥0, vâS. For any edge eâE, we are allowed to install an integer number x(e) of copies of e. The kSCND asks to simultaneously send demand d(v) from each source vâS along at most k paths to the sink t. A set of such paths can pass through an edge in G as long as the total demand along the paths does not exceed the capacity x(e)λ. The objective is to find a set P of paths of G that minimize the installing cost âeâEx(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.
Journal: Discrete Optimization - Volume 22, Part B, November 2016, Pages 328-340