Geodesic
On the problem of maximizing a modular function in the geometric lattice
The Bulletin of Irkutsk State University. Series Mathematics, Tome 6 (2013) no. 1, pp. 2-13 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{IIGUM_2013_6_1_a0,
     author = {V. A. Baransky and M. Yu. Vyplov and V. P. Il'ev},
     title = {On the problem of maximizing a modular function in the geometric lattice},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {2--13},
     year = {2013},
     volume = {6},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2013_6_1_a0/}
}
TY  - JOUR
AU  - V. A. Baransky
AU  - M. Yu. Vyplov
AU  - V. P. Il'ev
TI  - On the problem of maximizing a modular function in the geometric lattice
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2013
SP  - 2
EP  - 13
VL  - 6
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2013_6_1_a0/
LA  - ru
ID  - IIGUM_2013_6_1_a0
ER  - 
%0 Journal Article
%A V. A. Baransky
%A M. Yu. Vyplov
%A V. P. Il'ev
%T On the problem of maximizing a modular function in the geometric lattice
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2013
%P 2-13
%V 6
%N 1
%U http://geodesic.mathdoc.fr/item/IIGUM_2013_6_1_a0/
%G ru
%F IIGUM_2013_6_1_a0
V. A. Baransky; M. Yu. Vyplov; V. P. Il'ev. On the problem of maximizing a modular function in the geometric lattice. The Bulletin of Irkutsk State University. Series Mathematics, Tome 6 (2013) no. 1, pp. 2-13. http://geodesic.mathdoc.fr/item/IIGUM_2013_6_1_a0/

[1] M. Aigner, Kombinatornaya teoriya, Mir, M., 1982, 558 pp. | MR

[2] G. Birkgof, Teoriya reshetok, Nauka, M., 1984, 568 pp. | MR

[3] V. A. Baranskii, M. Yu. Vyplov, V. P. Ilev, “Minimizatsiya modulyarnykh i supermodulyarnykh funktsii na L-matroidakh”, Izv. Irkut. gos. un-ta. Ser. Matematika, 4:3 (2011), 42–53

[4] F. Dunstan, A. Ingleton, D. Welsh, “Supermatroids”, Combinatorics, Southend-on Sea, 1972, 72–122 | MR

[5] J. Edmonds, “Matroids and the greedy algorithm”, Math. Programming, 1:2 (1971), 127–136 | DOI | MR | Zbl

[6] D. Hausmann, B. Korte, “Lower bounds on the worst-case complexity of some oracle algorithms”, Discrete Math., 24:3 (1978), 261–276 | DOI | MR | Zbl

[7] Th. A. Jenkyns, “The efficacy of the "greedy" algorithm”, Proc. 7th Southeastern Conf. on Combinatorics, Graph Theory and Computing, eds. Hoffman F., Lesniak L., Mullin R., Reid K. B., Stanton R., Utilitas Math., Winnipeg, 1976, 341–350 | MR

[8] B. Korte, D. Hausmann, “An analysis of the greedy heuristic for independence systems”, Annals of Discrete Math., 2 (1978), 65–74 | DOI | MR | Zbl

[9] R. Rado, “Note on independence functions”, Proc. London. Math. Soc., 7:3 (1957), 300–320 | DOI | MR | Zbl