Approximating the -splittable capacitated network design problem

详细信息    查看全文

• 作者：Ehab Morsy p>ehabmorsy@gmail.com" class="auth_mail" title="E-mail the corresponding authorp>
• 关键词：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 pan id="mmlsi18" class="mathmlsrc">pan 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)pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">G=(V,E)pan>pan>pan> with edge weight pan id="mmlsi19" class="mathmlsrc">pan 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)≥0pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">w(e)≥0pan>pan>pan>, pan id="mmlsi20" class="mathmlsrc">pan 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∈Epan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">e∈Epan>pan>pan>. We are given a vertex pan id="mmlsi21" class="mathmlsrc">pan 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∈Vpan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">t∈Vpan>pan>pan> designated as a sink, a cable capacity pan id="mmlsi22" class="mathmlsrc">pan 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">λ>0pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">λ>0pan>pan>pan>, and a source set pan id="mmlsi23" class="mathmlsrc">pan 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⊆Vpan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">S⊆Vpan>pan>pan> with demand pan id="mmlsi24" class="mathmlsrc">pan 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)≥0pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">d(v)≥0pan>pan>pan>, pan id="mmlsi25" class="mathmlsrc">pan 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∈Span>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">v∈Span>pan>pan>. For any edge pan id="mmlsi20" class="mathmlsrc">pan 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∈Epan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">e∈Epan>pan>pan>, we are allowed to install an integer number pan id="mmlsi27" class="mathmlsrc">pan 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)pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">x(e)pan>pan>pan> of copies of pan id="mmlsi28" class="mathmlsrc">pan 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">epan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">epan>pan>pan>. The kSCND asks to simultaneously send demand pan id="mmlsi29" class="mathmlsrc">pan 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)pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">d(v)pan>pan>pan> from each source pan id="mmlsi25" class="mathmlsrc">pan 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∈Span>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">v∈Span>pan>pan> along at most pan id="mmlsi17" class="mathmlsrc">pan 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">kpan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">kpan>pan>pan> paths to the sink pan id="mmlsi32" class="mathmlsrc">pan 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">tpan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">tpan>pan>pan>. A set of such paths can pass through an edge in pan id="mmlsi33" class="mathmlsrc">pan 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">Gpan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">Gpan>pan>pan> as long as the total demand along the paths does not exceed the capacity pan id="mmlsi34" class="mathmlsrc">pan 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)λpan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">x(e)λpan>pan>pan>. The objective is to find a set pan id="mmlsi35" class="mathmlsrc">pan 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">Ppan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">pt">Ppan>pan>pan> of paths of pan id="mmlsi33" class="mathmlsrc">pan 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">Gpan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">Gpan>pan>pan> that minimize the installing cost pan id="mmlsi37" class="mathmlsrc">pan 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∈Ex(e)w(e)pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">∑e∈Ex(e)w(e)pan>pan>pan>. In this paper, we propose a pan id="mmlsi38" class="mathmlsrc">pan 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+ρ_{pan class="smallcaps">STpan>})pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">((k+1)/k+ρps>STps>)pan>pan>pan>-approximation algorithm to the kSCND, where pan id="mmlsi39" class="mathmlsrc">pan 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">ρ_{pan class="smallcaps">STpan>}pan>pan class="mathContainer hidden">pan class="mathCode">gif" overflow="scroll">ρps>STps>pan>pan>pan> is any approximation ratio achievable for the Steiner tree problem.