On the problem of maximizing a modular function in the geometric lattice

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

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

Abstract: The problem of maximizing a modular set function on order ideal in the finite geometric lattice is considered. Possibility of generalizing the Rado–Edmonds theorem is studied. A performance guarantee of the greedy algorithm generalizing the known Jenkyns–Korte–Hausmann bound for the problem of maximizing an additive function on independence system is obtained.

Keywords: modular function; geometric lattice; order ideal; $L$-matroid; greedy algorithm; performance guarantee.

UDC: 519.1, 519.8