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.
@cite_14: Let @math be a finite lattice and let @math be a positive integer. A function @math is said to be submodular if @math for all @math . In this paper we study submodular functions when @math is a diamond. Given oracle access to @math we are interested in finding @math such that @math as efficiently as possible. We establish a min--max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron; and a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular @math and an integer @math such that @math , there is a proof of this fact which can be verified in time polynomial in @math and @math ; and a pseudo-polynomial time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular @math one can find @math in time bounded by a polynomial in @math and @math .
Recently, researchers considered submodular functions on non-distributive lattices. It is known that a lattice is non-distributive if it contains as a sublattice either the pentagon @math or the diamond @math . Krokhin and Larose @cite_5 proved tractability for the pentagon case, using nested applications of a submodular minimization algorithm. The case of the diamond was considered by Kuivinen @cite_14 , who proved pseudo-polynomiality of the problem. The case of general non-distributive lattices is still open.