In 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), August 2011.

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(\bx)+f(\by)\ge f(\bx \sqcap \by)+f(\bx \sqcup \by)$ where the domain
of each variable $x_i$ corresponds to nodes of a rooted binary tree, and operations $\sqcap,\sqcup$ are defined
with respect to this tree. Special cases include previously studied $L^\natural$-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^\natural$-convex functions with bisubmodular minimization algorithms.