---
res:
bibo_abstract:
- 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.
@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Vladimir Kolmogorov
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1007/978-3-642-22993-0_37
bibo_volume: 6907
dct_date: 2011^xs_gYear
dct_publisher: Springer@
dct_title: 'Submodularity on a tree: Unifying Submodularity on a tree: Unifying
L-convex and bisubmodular functions convex and bisubmodular functions@'
...