کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141705 | 957085 | 2008 | 17 صفحه PDF | دانلود رایگان |

Does a given system of linear equations Ax=b have a non-negative integer solution? This is a fundamental question in many areas, such as operations research, number theory, and statistics. In terms of optimization, this is called an integer feasibility problem. A generalized integer feasibility problem is to find b such that there does not exist a non-negative integral solution in the system with a given AA. One such problem is the well-known Frobenius problem . In this paper we study the generalized integer feasibility problem and also the multi-dimensional Frobenius problem. To study a family of systems with no non-negative integer solution, we focus on a commutative semigroup generated by a finite subset of ZdZd and its saturation. An element in the difference between 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. As examples we consider some three- and four-way contingency tables from statistics and apply our results to them. Then we discuss the time complexities of our algorithms.
Journal: Discrete Optimization - Volume 5, Issue 1, February 2008, Pages 36–52