  In this thesis I explore challenging discrete energy minimization problems
that arise mainly in the context of computer vision tasks. This work motivates
the use of such "hard-to-optimize" non-submodular functionals, and proposes
methods and algorithms to cope with the NP-hardness of their optimization.
Consequently, this thesis revolves around two axes: applications and
approximations. The applications axis motivates the use of such
"hard-to-optimize" energies by introducing new tasks. As the energies become
less constrained and structured one gains more expressive power for the
objective function achieving more accurate models. Results show how
challenging, hard-to-optimize, energies are more adequate for certain computer
vision applications. To overcome the resulting challenging optimization tasks
the second axis of this thesis proposes approximation algorithms to cope with
the NP-hardness of the optimization. Experiments show that these new methods
yield good results for representative challenging problems.
