Approximating the -splittable capacitated network design problem

详细信息    查看全文

• 作者：Ehab Morsy ^{ehabmorsy@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Approximation algorithms ; Graph algorithms ; Routing problems ; Network optimization
• 刊名：Discrete Optimization
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：22
• 期：part_PB
• 页码：328-340
• 全文大小：777 K

文摘

We consider the k-Splittable Capacitated Network Design Problem   (kSCND) in a graph G=(V,E)$G=(V,E)$ with edge weight w(e)≥0$w\left(e\right)\ge 0$, e∈E$e\in E$. We are given a vertex t∈V$t\in V$ designated as a sink, a cable capacity 14c8443d7b9a729446f7adc9bed7a" title="Click to view the MathML source">λ>0$\lambda >0$, and a source set S⊆V$S\subseteq V$ with demand d(v)≥0$d\left(v\right)\ge 0$, v∈S$v\in S$. For any edge e∈E$e\in E$, we are allowed to install an integer number x(e)$x\left(e\right)$ of copies of e$e$. The kSCND asks to simultaneously send demand d(v)$d\left(v\right)$ from each source v∈S$v\in S$ along at most k$k$ paths to the sink t$t$. A set of such paths can pass through an edge in G$G$ as long as the total demand along the paths does not exceed the capacity x(e)λ$x\left(e\right)\lambda$. The objective is to find a set P$\mathcal{P}$ of paths of G$G$ that minimize the installing cost c309e2707014c1" title="Click to view the MathML source">∑_e∈Ex(e)w(e)${\sum }_{e\in E}x\left(e\right)w\left(e\right)$. In this paper, we propose a ((k+1)/k+ρ_ST)$((k+1)/k+{\rho }_{\text{<small-caps>ST</small-caps>}})$-approximation algorithm to the kSCND, where ρ_ST${\rho }_{\text{<small-caps>ST</small-caps>}}$ is any approximation ratio achievable for the Steiner tree problem.