Trichotomy for Integer Linear Systems Based on Their Sign Patterns
Kei Kimura, Kazuhisa Makino · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2012
In this paper, we consider solving the integer linear systems, i.e., given a matrix A in R^{m*n}, a vector b in R^m, and a positive integer d, to compute an integer vector x in D^n such that Ax 1. This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.