  In this paper, we propose the first exact algorithm for minimizing the
difference of two submodular functions (D.S.), i.e., the discrete version of
the D.C. programming problem. The developed algorithm is a
branch-and-bound-based algorithm which responds to the structure of this
problem through the relationship between submodularity and convexity. The D.S.
programming problem covers a broad range of applications in machine learning
because this generalizes the optimization of a wide class of set functions. We
empirically investigate the performance of our algorithm, and illustrate the
difference between exact and approximate solutions respectively obtained by the
proposed and existing algorithms in feature selection and discriminative
structure learning.
