|
Bulletin of Irkutsk State University. Series Mathematics, 2011, Volume 4, Issue 3, Pages 42–53
(Mi iigum115)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Minimizing modular and supermodular functions on $L$-matroids
V. A. Baranskia, M. Yu. Vyplovb, V. P. Il'evb a 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.
Citation:
V. A. Baranski, M. Yu. Vyplov, V. P. Il'ev, “Minimizing modular and supermodular functions on $L$-matroids”, Bulletin of Irkutsk State University. Series Mathematics, 4:3 (2011), 42–53
Linking options:
https://www.mathnet.ru/eng/iigum115 https://www.mathnet.ru/eng/iigum/v4/i3/p42
|
Statistics & downloads: |
Abstract page: | 263 | Full-text PDF : | 153 | References: | 48 |
|