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 hmlsrc">hImg" 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)hContainer hidden">hCode">h altimg="si18.gif" overflow="scroll">G=(V,E)h> with edge weight hmlsrc">hImg" 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)≥0hContainer hidden">hCode">h altimg="si19.gif" overflow="scroll">w(e)≥0h>, hmlsrc">hImg" 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∈EhContainer hidden">hCode">h altimg="si20.gif" overflow="scroll">e∈Eh>. We are given a vertex hmlsrc">hImg" 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∈VhContainer hidden">hCode">h altimg="si21.gif" overflow="scroll">t∈Vh> designated as a sink, a cable capacity hmlsrc">hImg" 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">λ>0hContainer hidden">hCode">h altimg="si22.gif" overflow="scroll">λ>0h>, and a source set hmlsrc">hImg" 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⊆VhContainer hidden">hCode">h altimg="si23.gif" overflow="scroll">S⊆Vh> with demand hmlsrc">hImg" 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)≥0hContainer hidden">hCode">h altimg="si24.gif" overflow="scroll">d(v)≥0h>, hmlsrc">hImg" 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∈ShContainer hidden">hCode">h altimg="si25.gif" overflow="scroll">v∈Sh>. For any edge hmlsrc">hImg" 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∈EhContainer hidden">hCode">h altimg="si20.gif" overflow="scroll">e∈Eh>, we are allowed to install an integer number hmlsrc">hImg" 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)hContainer hidden">hCode">h altimg="si27.gif" overflow="scroll">x(e)h> of copies of hmlsrc">hImg" 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">ehContainer hidden">hCode">h altimg="si28.gif" overflow="scroll">eh>. The kSCND asks to simultaneously send demand hmlsrc">hImg" 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)hContainer hidden">hCode">h altimg="si29.gif" overflow="scroll">d(v)h> from each source hmlsrc">hImg" 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∈ShContainer hidden">hCode">h altimg="si25.gif" overflow="scroll">v∈Sh> along at most hmlsrc">hImg" 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">khContainer hidden">hCode">h altimg="si17.gif" overflow="scroll">kh> paths to the sink hmlsrc">hImg" 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">thContainer hidden">hCode">h altimg="si32.gif" overflow="scroll">th>. A set of such paths can pass through an edge in hmlsrc">hImg" 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">GhContainer hidden">hCode">h altimg="si33.gif" overflow="scroll">Gh> as long as the total demand along the paths does not exceed the capacity hmlsrc">hImg" 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)λhContainer hidden">hCode">h altimg="si34.gif" overflow="scroll">x(e)λh>. The objective is to find a set hmlsrc">hImg" 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">PhContainer hidden">hCode">h altimg="si35.gif" overflow="scroll">hvariant="script">Ph> of paths of hmlsrc">hImg" 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">GhContainer hidden">hCode">h altimg="si33.gif" overflow="scroll">Gh> that minimize the installing cost hmlsrc">hImg" 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)hContainer hidden">hCode">h altimg="si37.gif" overflow="scroll">∑e∈Ex(e)w(e)h>. In this paper, we propose a hmlsrc">hImg" 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+ρ_ST)hContainer hidden">hCode">h altimg="si38.gif" overflow="scroll">((k+1)/k+ρST)h>-approximation algorithm to the kSCND, where hmlsrc">hImg" 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">ρ_SThContainer hidden">hCode">h altimg="si39.gif" overflow="scroll">ρSTh> is any approximation ratio achievable for the Steiner tree problem.