We present alpha-expansion beta-shrink moves, a simple generalization of the
widely-used alpha beta-swap and alpha-expansion algorithms for approximate
energy minimization. We show that in a certain sense, these moves dominate both
alpha beta-swap and alpha-expansion moves, but unlike previous generalizations
the new moves require no additional assumptions and are still solvable in
polynomial-time. We show promising experimental results with the new moves,
which we believe could be used in any context where alpha-expansions are
currently employed.