This article is cited in 1 paper

Minimizing modular and supermodular functions on $L$-matroids

V. A. Baranski^a, M. Yu. Vyplov^b, V. P. Il'ev<sup>b

a</sup> Ural State University, 51, Lenina pr., Ekaterinburg, 620083
^b Omsk State University, 55-a, Mira pr., Omsk, 644077

Abstract: A matroid can be viewed as an ideal of special kind in the boolean lattice. An analog of the notion of matroid for the case of finite geometric lattices is proposed and the following question is studied: whether a generalization of the Rado–Edmonds theorem can be proved? A bound on worst-case behaviour of the greedy algorithm for the problem of minimizing a supermodular function on a matroidal structure in the geomitric lattice is obtained.

Keywords: modular function, supermodular function, geometric lattice, $L$-matroid, greedy algorithm, performance guarantee.

UDC: 519.1, 519.8