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 non-saturation 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 27708-0320
|
|