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 A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$, a vector b∈R^m$b\in {\mathbb{R}}^m$, and a positive integer dede2072b1ecf8bf1c6901" title="Click to view the MathML source">d$d$, to compute an integer vector x∈Dⁿ$x\in D^n$ such that Ax≥b$Ax\ge b$ or to determine the infeasibility of the system, where m$m$ and n$n$ denote positive integers, R$\mathbb{R}$ denotes the set of reals, and D={0,1,…,d−1}$D=\{0,1,\dots ,d-1\}$. The problem is one of the most fundamental NP-hard problems in computer science.

For the problem, we propose a complexity index η$\eta$ which depends only on the sign pattern of A$A$. For a real edad069bc56ee59835a425" title="Click to view the MathML source">γ$\gamma$, let $\mathrm{ILS}\left(\gamma \right)$ denote the family of the problem instances I$I$ with η(I)=γ$\eta \left(I\right)=\gamma$. We then show the following trichotomy:

•

$\mathrm{ILS}\left(\gamma \right)$ is solvable in linear time, if γ<1$\gamma <1$,

•

$\mathrm{ILS}\left(\gamma \right)$ is weakly NP-hard and pseudo-polynomially solvable, if γ=1$\gamma =1$,

•

$\mathrm{ILS}\left(\gamma \right)$ is strongly NP-hard, if γ>1$\gamma >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.