Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions
LNCS
Vladimir Kolmogorov
We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms.
Springer
2011
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/3204
Kolmogorov V. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. In: Vol 6907. Springer; 2011:400-411. doi:<a href="https://doi.org/10.1007/978-3-642-22993-0_37">10.1007/978-3-642-22993-0_37</a>
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-22993-0_37
info:eu-repo/semantics/closedAccess