Approximating the -splittable capacitated network design problem
详细信息 查看全文
- 作者：Ehab Morsy <sup>ehabmorsy@gmail.com" class="auth_mail" title="E-mail the corresponding authorsup>
- 关键词：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 <span id="mmlsi18" class="mathmlsrc"><span 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)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> with edge weight <span id="mmlsi19" class="mathmlsrc"><span 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)≥0span><span class="mathContainer hidden"><span class="mathCode">span>span>span>, <span id="mmlsi20" class="mathmlsrc"><span 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∈Espan><span class="mathContainer hidden"><span class="mathCode">span>span>span>. We are given a vertex <span id="mmlsi21" class="mathmlsrc"><span 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∈Vspan><span class="mathContainer hidden"><span class="mathCode">span>span>span> designated as a sink, a cable capacity <span id="mmlsi22" class="mathmlsrc"><span 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">λ>0span><span class="mathContainer hidden"><span class="mathCode">span>span>span>, and a source set <span id="mmlsi23" class="mathmlsrc"><span 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⊆Vspan><span class="mathContainer hidden"><span class="mathCode">span>span>span> with demand <span id="mmlsi24" class="mathmlsrc"><span 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)≥0span><span class="mathContainer hidden"><span class="mathCode">span>span>span>, <span id="mmlsi25" class="mathmlsrc"><span 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∈Sspan><span class="mathContainer hidden"><span class="mathCode">span>span>span>. For any edge <span id="mmlsi20" class="mathmlsrc"><span 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∈Espan><span class="mathContainer hidden"><span class="mathCode">span>span>span>, we are allowed to install an integer number <span id="mmlsi27" class="mathmlsrc"><span 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)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> of copies of <span id="mmlsi28" class="mathmlsrc"><span 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">espan><span class="mathContainer hidden"><span class="mathCode">span>span>span>. The kSCND asks to simultaneously send demand <span id="mmlsi29" class="mathmlsrc"><span 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)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> from each source <span id="mmlsi25" class="mathmlsrc"><span 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∈Sspan><span class="mathContainer hidden"><span class="mathCode">span>span>span> along at most <span id="mmlsi17" class="mathmlsrc"><span 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">kspan><span class="mathContainer hidden"><span class="mathCode">span>span>span> paths to the sink <span id="mmlsi32" class="mathmlsrc"><span 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">tspan><span class="mathContainer hidden"><span class="mathCode">span>span>span>. A set of such paths can pass through an edge in <span id="mmlsi33" class="mathmlsrc"><span 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">Gspan><span class="mathContainer hidden"><span class="mathCode">span>span>span> as long as the total demand along the paths does not exceed the capacity <span id="mmlsi34" class="mathmlsrc"><span 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)λspan><span class="mathContainer hidden"><span class="mathCode">span>span>span>. The objective is to find a set <span id="mmlsi35" class="mathmlsrc"><span 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">Pspan><span class="mathContainer hidden"><span class="mathCode">span>span>span> of paths of <span id="mmlsi33" class="mathmlsrc"><span 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">Gspan><span class="mathContainer hidden"><span class="mathCode">span>span>span> that minimize the installing cost <span id="mmlsi37" class="mathmlsrc"><span 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">∑<sub>e∈Esub>x(e)w(e)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>. In this paper, we propose a <span id="mmlsi38" class="mathmlsrc"><span 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+ρ<sub><span class="smallcaps">STspan>sub>)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>-approximation algorithm to the kSCND, where <span id="mmlsi39" class="mathmlsrc"><span 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">ρ<sub><span class="smallcaps">STspan>sub>span><span class="mathContainer hidden"><span class="mathCode">span>span>span> is any approximation ratio achievable for the Steiner tree problem.