Francis Bach developed a convex-analytic treatment of submodular set functions and their applications to machine learning. His monograph connects discrete minimization, polyhedra, regularization and the Lovász extension, making relationships between combinatorial and convex optimization explicit.[ref]
For a finite ground set, submodularity is equivalent to diminishing marginal returns: adding an element to a smaller set gives at least as large a gain as adding it to a containing set. A coverage function illustrates this because objects already covered cannot contribute new coverage. The same structural property can support both direct selection problems and continuous optimization formulations; the modelling objective determines which connection is useful.
Articles by others on the same topic
There are currently no matching articles.