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