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 n id="mmlsi18" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si18.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=8d3d0c4c2f31d87eec37dddd1e020dba" title="Click to view the MathML source">G=(V,E)n>n class="mathContainer hidden">n class="mathCode">$G=(V,E)$n>n>n> with edge weight n id="mmlsi19" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si19.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=c45ca424c2231a14008b524067f37e68" title="Click to view the MathML source">w(e)≥0n>n class="mathContainer hidden">n class="mathCode">n>n>n>, n id="mmlsi20" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si20.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=8c80e91f2db20ff2e6260eba1983afe4" title="Click to view the MathML source">e&isin;En>n class="mathContainer hidden">n class="mathCode">$e\&isi<font\; color="red">n</font>;E$n>n>n>. We are given a vertex n id="mmlsi21" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si21.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=139ea5d98ff958e3efa17d2753a35330" title="Click to view the MathML source">t&isin;Vn>n class="mathContainer hidden">n class="mathCode">$t\&isi<font\; color="red">n</font>;V$n>n>n> designated as a sink, a cable capacity n id="mmlsi22" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si22.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=bbb14c8443d7b9a729446f7adc9bed7a" title="Click to view the MathML source">λ>0n>n class="mathContainer hidden">n class="mathCode">n>n>n>, and a source set n id="mmlsi23" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si23.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=845743b2e92a8a673b8403d0189f08d7" title="Click to view the MathML source">S⊆Vn>n class="mathContainer hidden">n class="mathCode">$S\subseteq V$n>n>n> with demand n id="mmlsi24" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si24.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=a9895895f7d41274b57a25e6554cddb3" title="Click to view the MathML source">d(v)≥0n>n class="mathContainer hidden">n class="mathCode">n>n>n>, n id="mmlsi25" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si25.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=f4cafc1cde1b1fb24c8a2ce243676c0f" title="Click to view the MathML source">v&isin;Sn>n class="mathContainer hidden">n class="mathCode">$v\&isi<font\; color="red">n</font>;S$n>n>n>. For any edge n id="mmlsi20" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si20.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=8c80e91f2db20ff2e6260eba1983afe4" title="Click to view the MathML source">e&isin;En>n class="mathContainer hidden">n class="mathCode">$e\&isi<font\; color="red">n</font>;E$n>n>n>, we are allowed to install an integer number n id="mmlsi27" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si27.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=c9dce8a422eefde76e948f6a1bb6859b" title="Click to view the MathML source">x(e)n>n class="mathContainer hidden">n class="mathCode">$x\left(e\right)$n>n>n> of copies of n id="mmlsi28" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si28.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=084a6b04dcc4c4f71f4ee818883a1b8f" title="Click to view the MathML source">en>n class="mathContainer hidden">n class="mathCode">$e$n>n>n>. The kSCND asks to simultaneously send demand n id="mmlsi29" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si29.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=702cfcfb038f100fa9e959459d2d188d" title="Click to view the MathML source">d(v)n>n class="mathContainer hidden">n class="mathCode">$d\left(v\right)$n>n>n> from each source n id="mmlsi25" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si25.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=f4cafc1cde1b1fb24c8a2ce243676c0f" title="Click to view the MathML source">v&isin;Sn>n class="mathContainer hidden">n class="mathCode">$v\&isi<font\; color="red">n</font>;S$n>n>n> along at most n id="mmlsi17" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si17.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=0ce2d8c804f04e1f6d047d50a4b48eb2" title="Click to view the MathML source">kn>n class="mathContainer hidden">n class="mathCode">$k$n>n>n> paths to the sink n id="mmlsi32" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si32.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=50e1f33703b04b19c0cea56cfa928fa1" title="Click to view the MathML source">tn>n class="mathContainer hidden">n class="mathCode">$t$n>n>n>. A set of such paths can pass through an edge in n id="mmlsi33" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si33.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=00db7f01f54425bbb6849482e08ba616" title="Click to view the MathML source">Gn>n class="mathContainer hidden">n class="mathCode">$G$n>n>n> as long as the total demand along the paths does not exceed the capacity n id="mmlsi34" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si34.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=d471d4d8a900d13c5842026303d9ddf0" title="Click to view the MathML source">x(e)λn>n class="mathContainer hidden">n class="mathCode">$x\left(e\right)\lambda$n>n>n>. The objective is to find a set n id="mmlsi35" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si35.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=b9c908b487e3df5bbadfd9b7fac7010d" title="Click to view the MathML source">Pn>n class="mathContainer hidden">n class="mathCode">n>n>n> of paths of n id="mmlsi33" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si33.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=00db7f01f54425bbb6849482e08ba616" title="Click to view the MathML source">Gn>n class="mathContainer hidden">n class="mathCode">$G$n>n>n> that minimize the installing cost n id="mmlsi37" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si37.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=39c08bd0821aa787e7c309e2707014c1" title="Click to view the MathML source">∑_e&isin;Ex(e)w(e)n>n class="mathContainer hidden">n class="mathCode">${\sum }_{e\&isi<font\; color="red">n</font>;E}x\left(e\right)w\left(e\right)$n>n>n>. In this paper, we propose a n id="mmlsi38" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si38.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=0958fbeda811cc01f7d05b067e7909db" title="Click to view the MathML source">((k+1)/k+ρ_{n class="smallcaps">STn>})n>n class="mathContainer hidden">n class="mathCode">n>n>n>-approximation algorithm to the kSCND, where n id="mmlsi39" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616300603&_mathId=si39.gif&_user=111111111&_pii=S1572528616300603&_rdoc=1&_issn=15725286&md5=b8b31da37bd734329db1656ebbd28d8e" title="Click to view the MathML source">ρ_{n class="smallcaps">STn>}n>n class="mathContainer hidden">n class="mathCode">${\rho }_{\text{<small-caps>ST</small-caps>}}$n>n>n> is any approximation ratio achievable for the Steiner tree problem.