Mathematics – Statistics Theory
Scientific paper
2006-03-04
Discrete Optimization, Volume 5, Issue 1 (2008) p36-52
Mathematics
Statistics Theory
This paper has been published in Discrete Optimization, Volume 5, Issue 1 (2008) p36-52
Scientific paper
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.
Takemura Akimichi
Yoshida Ruriko
No associations
LandOfFree
A generalization of the integer linear infeasibility problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A generalization of the integer linear infeasibility problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A generalization of the integer linear infeasibility problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-618914