  Motivated by problems in optimization we study the sparsity of the solutions
to systems of linear Diophantine equations and linear integer programs, i.e.,
the number of non-zero entries of a solution, which is often referred to as the
$\ell_0$-norm. Our main results are improved bounds on the $\ell_0$-norm of
sparse solutions to systems $A x = b$, where $A \in \mathbb{Z}^{m \times n}$,
$b \in \mathbb{Z}^m$ and $x$ is either a general integer vector (lattice case)
or a non-negative integer vector (semigroup case). In the lattice case and
certain scenarios of the semigroup case, we give polynomial time algorithms for
computing solutions with $\ell_0$-norm satisfying the obtained bounds.
