  The Gershgorin Circle Theorem is a well-known and efficient method for
bounding the eigenvalues of a matrix in terms of its entries. If $A$ is a
symmetric matrix, by writing $A = B + x{\bf 1}$, where ${\bf 1}$ is the matrix
with unit entries, we consider the problem of choosing $x$ to give the optimal
Gershgorin bound on the eigenvalues of $B$, which then leads to one-sided
bounds on the eigenvalues of $A$. We show that this $x$ can be found by an
efficient linear program (whose solution can in may cases be written in closed
form), and we show that for large classes of matrices, this shifting method
beats all existing piecewise linear or quadratic bounds on the eigenvalues. We
also apply this shifting paradigm to some nonlinear estimators and show that
under certain symmetries this also gives rise to a tractable linear program. As
an application, we give a novel bound on the lowest eigenvalue of a adjacency
matrix in terms of the "top two" or "bottom two" degrees of the corresponding
graph, and study the efficacy of this method in obtaining sharp eigenvalue
estimates for certain classes of matrices.
