Approximating the k-splittable capacitated network design problem

作者：Morsy Ehab^*

来源：Discrete Optimization, 2016, 22: 328-340.

DOI：10.1016/j.disopt.2016.09.001

• Approximation algorithms
• Graph algorithms
• Routing problems
• Network optimization

We consider the k-Splittable Capacitated Network Design Problem (kSCND) in a graph G = (V, E) with edge weight w(e) >= 0, e E E. We are given a vertex t E V designated as a sink, a cable capacity lambda > 0, and a source set S subset of V with demand d(v) >= 0, v E S. For any edge e 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 E 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)lambda. The objective is to find a set P of paths of G that minimize the installing cost Sigma(e is an element of E) x(e)w(e).In this paper, we propose a ((k + 1)/k + P-ST)-approximation algorithm to the kSCND, where P-ST is any approximation ratio achievable for the Steiner tree problem.

• 出版日期2016-11