Note on pseudolattices, lattices and submodular linear programs

Note on pseudolattices, lattices and submodular linear programs

0.00 Avg rating0 Votes
Article ID: iaor20091394
Country: Netherlands
Volume: 5
Issue: 2
Start Page Number: 489
End Page Number: 500
Publication Date: May 2008
Journal: Discrete Optimization
Authors: ,
Abstract:

A pseudolattice L is a poset with lattice-type binary operations. Given a submodular function r : L → ℝ and a modular representation of the pseudolattice as a family of subsets of a set U with certain compatibility properties, we demonstrate that the corresponding umestricted linear program relative to the representing set family can be solved by a greedy algorithm. This complements the Monge algorithm of Dietrich and Hoffman for the associated dual linear program. We furthermore show that our Monge and greedy algorithms are generally optimal for nonnegative submodular linear programs and their duals (relative to L). Finally, we show that L actually is a distributive lattice with the same supremum operation. Using Birkhoff's representation theorem for distributive lattices, we construct a suitable weight function on P that allows us to reduce the problems to generalized polymatroids.

Reviews

Required fields are marked *. Your email address will not be published.