|
|
Bulletin of Irkutsk State University. Series Mathematics, 2013, Volume 6, Issue 1, Pages 2–13
(Mi iigum1)
|
|
|
|
On the problem of maximizing a modular function in the geometric lattice
V. A. Baranskya, M. Yu. Vyplovb, V. P. Il'evb a 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.
Citation:
V. A. Baransky, M. Yu. Vyplov, V. P. Il'ev, “On the problem of maximizing a modular function in the geometric lattice”, Bulletin of Irkutsk State University. Series Mathematics, 6:1 (2013), 2–13
Linking options:
https://www.mathnet.ru/eng/iigum1 https://www.mathnet.ru/eng/iigum/v6/i1/p2
|
|