Computing holes in semi-groups and its applications to transportation problems
| dc.creator | Hemmecke, Raymond | |
| dc.creator | Takemura, Akimichi | |
| dc.creator | Yoshida, Ruriko | |
| dc.date | 2006-07-24 | |
| dc.date | 2009-04-09 | |
| dc.date.accessioned | 2026-07-07T13:01:47Z | |
| dc.date.available | 2026-07-07T13:01:47Z | |
| dc.description | An integer feasibility problem is a fundamental problem in many areas, such as operations research, number theory, and statistics. To study a family of systems with no nonnegative integer solution, we focus on a commutative semigroup generated by a finite set of vectors in $\Z^d$ and its saturation. In this paper we present an algorithm to compute an explicit description for the set of holes which is the difference of a semi-group $Q$ generated by the vectors and its saturation. We apply our procedure to compute an infinite family of holes for the semi-group of the $3\times 4\times 6$ transportation problem. Furthermore, we give an upper bound for the entries of the holes when the set of holes is finite. Finally, we present an algorithm to find all $Q$-minimal saturation points of $Q$. | |
| dc.description | Presentation has been improved according to comments by referees. This manuscript has been accepted to "Contributions to Discrete Mathematics" | |
| dc.identifier | https://arxiv.org/abs/math/0607599 | |
| dc.identifier | http://arxiv.org/abs/math/0607599 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226265 | |
| dc.subject | Combinatorics | |
| dc.title | Computing holes in semi-groups and its applications to transportation problems | |
| dc.type | text |