Submodular Function Minimization and Polarity
  Using polarity, we give an outer polyhedral approximation for the epigraph of
set functions. For a submodular function, we prove that the corresponding polar
relaxation is exact; hence, it is equivalent to the Lov\'asz extension. The
polar approach provides an alternative proof for the convex hull description of
the epigraph of a submodular function. Computational experiments show that the
inequalities from outer approximations can be effective as cutting planes for
solving submodular as well as non-submodular set function minimization
problems.
