|
This article is cited in 3 scientific papers (total in 3 papers)
Problems on independence systems solvable by the greedy algorithm
V. P. Ilyev
Abstract:
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.
Received: 10.04.2007 Revised: 26.01.2009
Citation:
V. P. Ilyev, “Problems on independence systems solvable by the greedy algorithm”, Diskr. Mat., 21:4 (2009), 85–94; Discrete Math. Appl., 19:5 (2009), 515–522
Linking options:
https://www.mathnet.ru/eng/dm1074https://doi.org/10.4213/dm1074 https://www.mathnet.ru/eng/dm/v21/i4/p85
|
Statistics & downloads: |
Abstract page: | 521 | Full-text PDF : | 255 | References: | 68 | First page: | 16 |
|