A generalization of the integer linear infeasibility problem
| dc.creator | Takemura, Akimichi | |
| dc.creator | Yoshida, Ruriko | |
| dc.date | 2006-03-04 | |
| dc.date | 2008-04-12 | |
| dc.date.accessioned | 2026-07-07T09:32:05Z | |
| dc.date.available | 2026-07-07T09:32:05Z | |
| dc.description | Does a given system of linear equations with nonnegative constraints have an integer solution? This is a fundamental question in many areas. In statistics this problem arises in data security problems for contingency table data and also is closely related to non-squarefree elements of Markov bases for sampling contingency tables with given marginals. To study a family of systems with no integer solution, we focus on a commutative semigroup generated by a finite subset of $\Z^d$ and its saturation. An element in the difference of the semigroup and its saturation is called a ``hole''. We show the necessary and sufficient conditions for the finiteness of the set of holes. Also we define fundamental holes and saturation points of a commutative semigroup. Then, we show the simultaneous finiteness of the set of holes, the set of non-saturation points, and the set of generators for saturation points. We apply our results to some three- and four-way contingency tables. Then we will discuss the time complexities of our algorithms. | |
| dc.description | This paper has been published in Discrete Optimization, Volume 5, Issue 1 (2008) p36-52 | |
| dc.identifier | https://arxiv.org/abs/math/0603108 | |
| dc.identifier | http://arxiv.org/abs/math/0603108 | |
| dc.identifier | Discrete Optimization, Volume 5, Issue 1 (2008) p36-52 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158683 | |
| dc.subject | Statistics Theory | |
| dc.subject | Combinatorics | |
| dc.subject | Computation | |
| dc.title | A generalization of the integer linear infeasibility problem | |
| dc.type | text |