We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions @math satisfying @math where the domain of each variable @math corresponds to nodes of a rooted binary tree, and operations @math are defined with respect to this tree. Special cases include previously studied @math -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 @math -convex functions with bisubmodular minimization algorithms.
@cite_5: Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a supermodular function which is defined on a product of @math copies of a fixed finite lattice and given by an oracle. We exhibit a large class of finite lattices for which this problem can be solved in oracle-polynomial time in @math . We also obtain new large classes of tractable maximum constraint satisfaction problems.
Combining multimorphisms Finally, we mention that some constructions, namely Cartesian products and Malt'stev products , can be used for obtaining new tractable classes of binary multimoprhisms from existing ones @cite_5 . Note, Krokhin and Larose @cite_5 formulated these constructions only for lattice multimorphisms @math , but the proof in @cite_5 actually applies to arbitrary binary multimorphisms @math .