Geodesic
Problems on independence systems solvable by the greedy algorithm
Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 85-94 
V. P. Ilyev. Problems on independence systems solvable by the greedy algorithm. Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 85-94. http://geodesic.mathdoc.fr/item/DM_2009_21_4_a7/
@article{DM_2009_21_4_a7,
     author = {V. P. Ilyev},
     title = {Problems on independence systems solvable by the greedy algorithm},
     journal = {Diskretnaya Matematika},
     pages = {85--94},
     year = {2009},
     volume = {21},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_4_a7/}
}
TY  - JOUR
AU  - V. P. Ilyev
TI  - Problems on independence systems solvable by the greedy algorithm
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 85
EP  - 94
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_4_a7/
LA  - ru
ID  - DM_2009_21_4_a7
ER  - 
%0 Journal Article
%A V. P. Ilyev
%T Problems on independence systems solvable by the greedy algorithm
%J Diskretnaya Matematika
%D 2009
%P 85-94
%V 21
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2009_21_4_a7/
%G ru
%F DM_2009_21_4_a7

Voir la notice de l'article provenant de la source Math-Net.Ru

One of the key results of the theory of matroids is the well-known Rado–Edmonds theorem which states that the problem of maximising an additive function on an independence system is solvable by the greedy algorithm if and only if the independence system is a matroid. Many generalisations of the Rado–Edmonds theorem were related in main with extension of the set of feasible solutions of the maximisation problem, as a rule an independence system was replaced by an accessible set system. Extension of the class of objective functions was also accompanied by extension of the feasible sets. In this paper, we investigate the maximisation problems of nonadditive functions of sets on independence systems. We suggest a characterisation of the class of objective functions of the problems on matroids which are solvable by the greedy algorithm. We proved a generalisation of the Rado–Edmonds theorem for the maximisation problem on the independence system of a nonadditive function of a given class.

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

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

[3] Korte B., Lovász L., “Greedoids and linear objective functions”, SIAM J. Alg. Discrete Math., 5:2 (1984), 229–238 | DOI | MR | Zbl

[4] Goetschel R. H., “Linear objective functions on certain classes of greedoids”, Discrete Appl. Math., 14:1 (1986), 11–16 | DOI | MR | Zbl

[5] Shenmaier V. V., “Maksimizatsiya lineinoi tselevoi funktsii s pomoschyu zhadnogo algoritma”, Diskretnyi analiz i issledovanie operatsii, cer. 1, 6:4 (1999), 104–120 | MR | Zbl

[6] Helman P., Moret B. M. E., Shapiro N. D., “An exact characterization of greedy structures”, SIAM J. Discrete Math., 6:2 (1993), 274–283 | DOI | MR | Zbl

[7] Glebov N. I., “Ob odnom klasse zadach vypuklogo tselochislennogo programmirovaniya”, Upravlyaemye sistemy, 11, 1973, 38–42

[8] Glebov N. I., Shenmaier V. V., “O primenimosti algoritma pokoordinatnogo pod'ema k zadacham tselochislennogo programmirovaniya”, Diskretnyi analiz i issledovanie operatsii, ser. 1, 7:4 (2000), 38–47 | MR | Zbl

[9] Korte B., Lovász L., “Mathematical structures underlying greedy algorithm”, Lect. Notes Comput. Sci., 117, 1981, 205–209 | MR | Zbl