Note on Pseudolattices, Lattices and Submodular Linear Programs

Faigle, Ulrich and Peis, Britta (2005) Note on Pseudolattices, Lattices and Submodular Linear Programs.
Technical Report , 17 p.
Submitted

Abstract

A pseudolattice L is a poset with lattice-type binary operations. Assuming that the pseudolattice permits a modular representation as a family of subsets of a set U with certain compatibility properties, we show that L actually is a distributive lattice with the same supremum operation. Given a submodular function r:L o R , we prove that the corresponding unrestricted 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 algorithm is generally optimal for nonnegative submodular linear programs and their duals (relative to L ).


Actions:
Download: [img] Postscript
Download (187kB) | Preview
Download: [img] PDF
Download (97kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: 4 (Google Scholar) |
Uncontrolled Keywords: greedy algorithm duality submodularity distributive lattices
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 06-XX Order, lattices, ordered algebraic structures > 06Dxx Distributive lattices > 06D50 Lattices and duality

    		•
    Divisions: UNSPECIFIED
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2006-513
    Depositing User: Prof. Dr. Ulrich Faigle
    Date Deposited: 08 Feb 2006 00:00
    Last Modified: 19 Dec 2011 09:44
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/513