Math @ Duke

Publications [#47936] of Ruriko Yoshida
search www.math.duke.edu.Papers Submitted
 A. Takemura and R. Yoshida, A generalization of the integer linear infeasibility problem,
Discrete Optimization
(2006) [math.ST/0603108]
(last updated on 2006/07/01)
Abstract: Does a given system of linear equations with
nonnegative constraints have an
integer solution? This problem appears in
many areas, such as
number theory, operations research, and
statistics. To study a
family of systems with no integer solution,
we focus on a
commutative semigroup generated by the
columns of its defining matrix.
In this paper we will study a commutative
semigroup generated by a finite
subset of $\Z^d$ and its saturation. We show
the necessary and sufficient
conditions for the given semigroup to have a
finite number of elements in
the difference between the semigroup and its
saturation.
Also we define fundamental holes and
saturation points of a
commutative semigroup. Then, we show the
simultaneous
finiteness of the
difference between the semigroup and its
saturation,
the set of nonsaturation points of the
semigroup, and the set of
generators for saturation points, which is a
set of generator of a monoid.
We apply our results to some three and four
dimensional contingency tables.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

