Trichotomy for Integer Linear Systems Based on Their Sign Patterns
Trichotomy for Integer Linear Systems Based on Their Sign Patterns
复制标题
基于符号模式的整数线性系统的三分法
DOI：
10.1016/j.dam.2015.07.004
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Kei Kimura and Kazuhisa Makino
中科院分区：
文献类型：
--
作者：
M. Nishikawara;K. Otani;Y. Ueda;and H. Yanada;Kei Kimura and Kazuhisa Makino
本文考虑求解整数线性系统，即给定一个矩阵a∈R mx n，一个向量b∈R m，一个正整数d，计算一个整数向量x∈d n使a x≥b或确定该系统的不可行性，其中m和n为正整数，R为实数集，d ={0,1，…，d−1}。这个问题是计算机科学中最基本的np困难问题之一。对于这个问题，我们提出了一个复杂度指标η，它只依赖于a的符号模式。对于一个实数γ，设ILS （γ）表示问题实例I的族，η (I)= γ。然后我们证明了以下三分法：•ILS （γ）在线性时间内可解，如果γ< 1，•ILS （γ）是弱NP-hard且伪多项式可解，如果γ= 1，•ILS （γ）是强NP-hard，如果γ> 1。例如，这包括以前的结果，即Horn系统和两变量每不等式（TVPI）系统可以在伪多项式时间内求解。
In this paper, we consider solving the integer linear systems, ie, given a matrix A∈ R m× n, a vector b∈ R m, and a positive integer d, to compute an integer vector x∈ D n such that A x≥ b or to determine the infeasibility of the system, where m and n denote positive integers, R denotes the set of reals, and D={0, 1,…, d− 1}. The problem is one of the most fundamental NP-hard problems in computer science. For the problem, we propose a complexity index η which depends only on the sign pattern of A. For a real γ, let ILS (γ) denote the family of the problem instances I with η (I)= γ. We then show the following trichotomy:• ILS (γ) is solvable in linear time, if γ< 1,• ILS (γ) is weakly NP-hard and pseudo-polynomially solvable, if γ= 1,• ILS (γ) is strongly NP-hard, if γ> 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.