Neighbors of the Origin for Four by Three Matrices

Scarf has defined a neighborhood system for families of integer programs where the right-hand side is allowed to vary. This system depends on a matrix A of constraint and objective function coefficients of the integer programs.

This paper characterizes the set of neighbors of the origin when A is four by three, showing that it may be described as the set of integer vectors in a union of two-dimensional polyhedra, where the number of polyhedra is quadratic in the bit size of A.