Trichotomy for integer linear systems based on their sign patterns

详细信息    查看全文

• 作者：Kei Kimura^a ; ^{kimura@cs.tut.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Kazuhisa Makino^b
• 关键词：Integer linear system ; Sign pattern ; Complexity index ; TVPI system ; Horn system
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 February 2016
• 年：2016
• 卷：200
• 期：Complete
• 页码：67-78
• 全文大小：441 K

文摘

In this paper, we consider solving the integer linear systems, i.e., given a matrix id="mmlsi3" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si3.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=052f1d3f841ea34a94470552b08b371f" title="Click to view the MathML source">A∈R^m×niner hidden">i3.gif" overflow="scroll">i>Ai>∈i mathvariant="double-struck">Ri>i>mi>×i>ni>, a vector id="mmlsi4" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si4.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=9d4ed8f407d2208e56d003ca7b5b9e37" title="Click to view the MathML source">b∈R^miner hidden">i4.gif" overflow="scroll">i>bi>∈i mathvariant="double-struck">Ri>i>mi>, and a positive integer id="mmlsi5" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si5.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=96899af1b4dede2072b1ecf8bf1c6901" title="Click to view the MathML source">diner hidden">i5.gif" overflow="scroll">i>di>, to compute an integer vector id="mmlsi6" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si6.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=77d2c7c10de03437851d746998662471" title="Click to view the MathML source">x∈Dⁿiner hidden">i6.gif" overflow="scroll">i>xi>∈i>Di>i>ni> such that id="mmlsi7" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si7.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=2911cfcb8e54324e7039891cd04fb755" title="Click to view the MathML source">Ax≥biner hidden">i7.gif" overflow="scroll">i>Ai>i>xi>≥i>bi> or to determine the infeasibility of the system, where id="mmlsi8" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si8.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=6effc502bed8438f786a87897bc6ca37" title="Click to view the MathML source">miner hidden">i8.gif" overflow="scroll">i>mi> and id="mmlsi9" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si9.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=c4a3e05320d6508e06a819342e89adb6" title="Click to view the MathML source">niner hidden">i9.gif" overflow="scroll">i>ni> denote positive integers, id="mmlsi10" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si10.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=a1c1f533003d823f66474ada1e4e5cad" title="Click to view the MathML source">Riner hidden">i10.gif" overflow="scroll">i mathvariant="double-struck">Ri> denotes the set of reals, and id="mmlsi11" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si11.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=4415b25a0ec9c8612139c2496468b849" title="Click to view the MathML source">D={0,1,…,d−1}iner hidden">i11.gif" overflow="scroll">i>Di>={0,1,…,i>di>−1}. The problem is one of the most fundamental NP-hard problems in computer science.

id="sp000015">For the problem, we propose a complexity index id="mmlsi12" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si12.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=7ee97540b65803e8e871bdf8360176ae" title="Click to view the MathML source">ηiner hidden">i12.gif" overflow="scroll">i>ηi> which depends only on the sign pattern of id="mmlsi13" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si13.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=39eb4b6412a5b79df919ff5cd22c9f60" title="Click to view the MathML source">Ainer hidden">i13.gif" overflow="scroll">i>Ai>. For a real id="mmlsi14" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si14.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=a32235c986edad069bc56ee59835a425" title="Click to view the MathML source">γiner hidden">i14.gif" overflow="scroll">i>γi>, let id="mmlsi15" class="mathmlsrc">itle="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si15.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=ad42610d58d4ef24d0a12a357415d8c0"><img class="imgLazyJSB inlineImage" height="16" width="44" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15003285-si15.gif">ipt><img height="16" border="0" style="vertical-align:bottom" width="44" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X15003285-si15.gif">ipt>iner hidden">i15.gif" overflow="scroll">iant="normal">i>ILSi>(i>γi>) denote the family of the problem instances id="mmlsi16" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si16.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=d5c65e09281ccd92efb53dfc265ecc9e" title="Click to view the MathML source">Iiner hidden">i16.gif" overflow="scroll">i>Ii> with id="mmlsi17" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si17.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=f53a0487d0dbbd73118a0164fe96d77e" title="Click to view the MathML source">η(I)=γiner hidden">i17.gif" overflow="scroll">i>ηi>(i>Ii>)=i>γi>. We then show the following trichotomy:

istitem" id="list_l000005">

•

id="p000005">id="mmlsi15" class="mathmlsrc">itle="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si15.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=ad42610d58d4ef24d0a12a357415d8c0"><img class="imgLazyJSB inlineImage" height="16" width="44" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15003285-si15.gif">ipt><img height="16" border="0" style="vertical-align:bottom" width="44" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X15003285-si15.gif">ipt>iner hidden">i15.gif" overflow="scroll">iant="normal">i>ILSi>(i>γi>) is solvable in linear time, if id="mmlsi19" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si19.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=1a7ff3144a022f6de2916850786c1a97" title="Click to view the MathML source">γ<1iner hidden">i19.gif" overflow="scroll">i>γi><1,

•

id="p000010">id="mmlsi15" class="mathmlsrc">itle="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si15.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=ad42610d58d4ef24d0a12a357415d8c0"><img class="imgLazyJSB inlineImage" height="16" width="44" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15003285-si15.gif">ipt><img height="16" border="0" style="vertical-align:bottom" width="44" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X15003285-si15.gif">ipt>iner hidden">i15.gif" overflow="scroll">iant="normal">i>ILSi>(i>γi>) is weakly NP-hard and pseudo-polynomially solvable, if id="mmlsi21" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si21.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=00eaa8c34977cce9b50d9a918275faf9" title="Click to view the MathML source">γ=1iner hidden">i21.gif" overflow="scroll">i>γi>=1,

•

id="p000015">id="mmlsi15" class="mathmlsrc">itle="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si15.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=ad42610d58d4ef24d0a12a357415d8c0"><img class="imgLazyJSB inlineImage" height="16" width="44" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15003285-si15.gif">ipt><img height="16" border="0" style="vertical-align:bottom" width="44" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X15003285-si15.gif">ipt>iner hidden">i15.gif" overflow="scroll">iant="normal">i>ILSi>(i>γi>) is strongly NP-hard, if id="mmlsi23" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003285&_mathId=si23.gif&_user=111111111&_pii=S0166218X15003285&_rdoc=1&_issn=0166218X&md5=7f871fa60b16f982637023e0c88f6adb" title="Click to view the MathML source">γ>1iner hidden">i23.gif" overflow="scroll">i>γi>>1.

This, for example, includes the previous results that Horn systems and two-variable-per-inequality (TVPI) systems can be solved in pseudo-polynomial time.