Istituto di Scienza e Tecnologie dell'Informazione     
Tardella F., Queyranne M. Minimizing submodular functions on finite sublattices of product spaces. Internal note IEI-B4-50, 1992.
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.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional