Minimizing submodular functions on finite sublattices of product spaces

An important consequence of the ellipsoid method in combinatorial optimization is the possibility of minimizing a submodular function on {0, 1} ? n in polynomial time. In this paper we show that this result can be extended to the case of functions defined on any sublattice of a product space. We also describe a way or representing a sublattice of a product space and give some conditions guaranteeing the existence of an extension of a given submodular or modular function from a sublattice to a larger one. As a consequence of this, we show that the notions of modularity and separability coincide for functions defined on any countable sublattice or a product space.