License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.613
URN: urn:nbn:de:0030-drops-34367
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3436/
Go to the corresponding LIPIcs Volume Portal

Kimura, Kei ; Makino, Kazuhisa

Trichotomy for Integer Linear Systems Based on Their Sign Patterns

pdf-format:
52.pdf (0.5 MB)

Abstract

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 <= b,
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 h which is based only on the sign pattern of A. For a real r, let ILS_=(r) denote the family of the problem instances I with h(I)=r. We then show the following trichotomy:

- ILS_=(r) is linearly solvable, if r < 1,

- ILS_=(r) is weakly NP-hard and pseudo-polynomially solvable, if r = 1, and

- ILS_=(r) is strongly NP-hard, if r > 1.

This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.

BibTeX - Entry

@InProceedings{kimura_et_al:LIPIcs:2012:3436,
  author =	{Kei Kimura and Kazuhisa Makino},
  title =	{{Trichotomy for Integer Linear Systems Based on Their Sign Patterns}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{613--623},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3436},
  URN =		{urn:nbn:de:0030-drops-34367},
  doi =		{10.4230/LIPIcs.STACS.2012.613},
  annote =	{Keywords: Integer linear system, Sign pattern, Complexity index, TVPI system, Horn system}
}

Keywords: Integer linear system, Sign pattern, Complexity index, TVPI system, Horn system
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI