Geodesic
Minimizing modular and supermodular functions on $L$-matroids
The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 3, pp. 42-53 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{IIGUM_2011_4_3_a3,
     author = {V. A. Baranski and M. Yu. Vyplov and V. P. Il'ev},
     title = {Minimizing modular and supermodular functions on $L$-matroids},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {42--53},
     year = {2011},
     volume = {4},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2011_4_3_a3/}
}
TY  - JOUR
AU  - V. A. Baranski
AU  - M. Yu. Vyplov
AU  - V. P. Il'ev
TI  - Minimizing modular and supermodular functions on $L$-matroids
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2011
SP  - 42
EP  - 53
VL  - 4
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2011_4_3_a3/
LA  - ru
ID  - IIGUM_2011_4_3_a3
ER  - 
%0 Journal Article
%A V. A. Baranski
%A M. Yu. Vyplov
%A V. P. Il'ev
%T Minimizing modular and supermodular functions on $L$-matroids
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2011
%P 42-53
%V 4
%N 3
%U http://geodesic.mathdoc.fr/item/IIGUM_2011_4_3_a3/
%G ru
%F IIGUM_2011_4_3_a3
V. A. Baranski; M. Yu. Vyplov; V. P. Il'ev. Minimizing modular and supermodular functions on $L$-matroids. The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 3, pp. 42-53. http://geodesic.mathdoc.fr/item/IIGUM_2011_4_3_a3/

[1] A. A. Ageev, V. P. Ilev, A. V. Kononov, A. S. Talevnin, “Vychislitelnaya slozhnost zadachi approksimatsii grafov”, Diskret. analiz i issledovanie operatsii. Ser. 1, 13:1 (2006), 3–15 | MR | Zbl

[2] M. Aigner, Kombinatornaya teoriya, Mir, M., 1982 | MR

[3] G. Birkgof, Teoriya struktur, Nauka, M., 1984 | MR

[4] V. P. Ilev, S. D. Ileva, “Zadachi minimizatsii supermodulyarnykh funktsii na matroidakh i komatroidakh”, Problemy optimizatsii i ekonomicheskie prilozheniya, Materialy IV Vseros. konf. (29 iyunya–4 iyulya 2009 g.), Poligraf. tsentr KAN, Omsk, 2009, 51–55

[5] V. R. Khachaturov, “Supermodulyarnye funktsii na reshetkakh”, Problemy prikladnoi matematiki i informatiki, Nauka, M., 1987, 251–262 | MR

[6] V. P. Cherenin, Reshenie nekotorykh kombinatornykh zadach optimalnogo planirovaniya metodom posledovatelnykh raschetov, Nauchno-metodicheskie materialy ekonomiko-matematicheskogo seminara Laboratorii ekonomiko-matematicheskikh metodov AN SSSR, 2, M., 1962

[7] F. Dunstan, A. Ingleton, D. Welsh, “Supermatroids”, Combinatorics, Southend-on Sea, 1972, 338–353 | MR

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

[9] O. Kariv, S. L. Hakimi, “An algorithmic approach to network location problems. II: The $p$-medians”, SIAM J. Appl. Math., 37:3 (1979), 539–560 | DOI | MR | Zbl

[10] V. R. Khachaturov, R. V. Khachaturov, R. V. Khachaturov, “Supermodular programming on lattices”, Computer Science J. of Moldova, 11:1 (31) (2003), 43–66 | MR

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