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 m>k-Splittable Capacitated Network Design Problem  m> (kSCND) in a graph mmlsi18" class="mathmlsrc">mulatext 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)mathContainer hidden">mathCode"><math altimg="si18.gif" overflow="scroll"><mi>Gmi><mo>=mo><mrow><mo>(mo><mi>Vmi><mo>,mo><mi>Emi><mo>)mo>mrow>math> with edge weight mmlsi19" class="mathmlsrc">mulatext 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)≥0mathContainer hidden">mathCode"><math altimg="si19.gif" overflow="scroll"><mi>wmi><mrow><mo>(mo><mi>emi><mo>)mo>mrow><mo>≥mo><mn>0mn>math>, mmlsi20" class="mathmlsrc">mulatext 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∈EmathContainer hidden">mathCode"><math altimg="si20.gif" overflow="scroll"><mi>emi><mo>∈mo><mi>Emi>math>. We are given a vertex mmlsi21" class="mathmlsrc">mulatext 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∈VmathContainer hidden">mathCode"><math altimg="si21.gif" overflow="scroll"><mi>tmi><mo>∈mo><mi>Vmi>math> designated as a sink, a cable capacity mmlsi22" class="mathmlsrc">mulatext 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">λ>0mathContainer hidden">mathCode"><math altimg="si22.gif" overflow="scroll"><mi>λmi><mo>>mo><mn>0mn>math>, and a source set mmlsi23" class="mathmlsrc">mulatext 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⊆VmathContainer hidden">mathCode"><math altimg="si23.gif" overflow="scroll"><mi>Smi><mo>⊆mo><mi>Vmi>math> with demand mmlsi24" class="mathmlsrc">mulatext 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)≥0mathContainer hidden">mathCode"><math altimg="si24.gif" overflow="scroll"><mi>dmi><mrow><mo>(mo><mi>vmi><mo>)mo>mrow><mo>≥mo><mn>0mn>math>, mmlsi25" class="mathmlsrc">mulatext 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∈SmathContainer hidden">mathCode"><math altimg="si25.gif" overflow="scroll"><mi>vmi><mo>∈mo><mi>Smi>math>. For any edge mmlsi20" class="mathmlsrc">mulatext 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∈EmathContainer hidden">mathCode"><math altimg="si20.gif" overflow="scroll"><mi>emi><mo>∈mo><mi>Emi>math>, we are allowed to install an integer number mmlsi27" class="mathmlsrc">mulatext 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)mathContainer hidden">mathCode"><math altimg="si27.gif" overflow="scroll"><mi>xmi><mrow><mo>(mo><mi>emi><mo>)mo>mrow>math> of copies of mmlsi28" class="mathmlsrc">mulatext 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">emathContainer hidden">mathCode"><math altimg="si28.gif" overflow="scroll"><mi>emi>math>. The kSCND asks to simultaneously send demand mmlsi29" class="mathmlsrc">mulatext 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)mathContainer hidden">mathCode"><math altimg="si29.gif" overflow="scroll"><mi>dmi><mrow><mo>(mo><mi>vmi><mo>)mo>mrow>math> from each source mmlsi25" class="mathmlsrc">mulatext 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∈SmathContainer hidden">mathCode"><math altimg="si25.gif" overflow="scroll"><mi>vmi><mo>∈mo><mi>Smi>math> along at most mmlsi17" class="mathmlsrc">mulatext 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">kmathContainer hidden">mathCode"><math altimg="si17.gif" overflow="scroll"><mi>kmi>math> paths to the sink mmlsi32" class="mathmlsrc">mulatext 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">tmathContainer hidden">mathCode"><math altimg="si32.gif" overflow="scroll"><mi>tmi>math>. A set of such paths can pass through an edge in mmlsi33" class="mathmlsrc">mulatext 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">GmathContainer hidden">mathCode"><math altimg="si33.gif" overflow="scroll"><mi>Gmi>math> as long as the total demand along the paths does not exceed the capacity mmlsi34" class="mathmlsrc">mulatext 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)λmathContainer hidden">mathCode"><math altimg="si34.gif" overflow="scroll"><mi>xmi><mrow><mo>(mo><mi>emi><mo>)mo>mrow><mi>λmi>math>. The objective is to find a set mmlsi35" class="mathmlsrc">mulatext 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">PmathContainer hidden">mathCode"><math altimg="si35.gif" overflow="scroll"><mi mathvariant="script">Pmi>math> of paths of mmlsi33" class="mathmlsrc">mulatext 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">GmathContainer hidden">mathCode"><math altimg="si33.gif" overflow="scroll"><mi>Gmi>math> that minimize the installing cost mmlsi37" class="mathmlsrc">mulatext 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">&sum;_e∈Ex(e)w(e)mathContainer hidden">mathCode"><math altimg="si37.gif" overflow="scroll"><msub><mrow><mo>&sum;mo>mrow><mrow><mi>emi><mo>∈mo><mi>Emi>mrow>msub><mi>xmi><mrow><mo>(mo><mi>emi><mo>)mo>mrow><mi>wmi><mrow><mo>(mo><mi>emi><mo>)mo>mrow>math>. In this paper, we propose a mmlsi38" class="mathmlsrc">mulatext 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+ρ_mallcaps">ST)mathContainer hidden">mathCode"><math altimg="si38.gif" overflow="scroll"><mrow><mo>(mo><mrow><mo>(mo><mi>kmi><mo>+mo><mn>1mn><mo>)mo>mrow><mo>/mo><mi>kmi><mo>+mo><msub><mrow><mi>ρmi>mrow><mrow><mtext>mall-caps>STmall-caps>mtext>mrow>msub><mo>)mo>mrow>math>-approximation algorithm to the kSCND, where mmlsi39" class="mathmlsrc">mulatext 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">ρ_mallcaps">STmathContainer hidden">mathCode"><math altimg="si39.gif" overflow="scroll"><msub><mrow><mi>ρmi>mrow><mrow><mtext>mall-caps>STmall-caps>mtext>mrow>msub>math> is any approximation ratio achievable for the m>Steiner tree problemm>.