Structural properties of greedoids |
| |
Authors: | Bernhard Korte László Lovász |
| |
Institution: | 1. Institut für ?konometrie und Operations Research Rheinische Friedrich—Wilhelms-Univ., Bonn, West-Germany 2. Mathematical Institute of the Loránd E?tv?s University, 1088, Budapest, Hungary
|
| |
Abstract: | Greedoids were introduced by the authors as generalizations of matroids providing a framework for the greedy algorithm. In
this paper they are studied from a structural aspect. Definitions of basic matroid-theoretical concepts such as rank and closure
can be generalized to greedoids, even though they loose some of their fundamental properties. The rank function of a greedoid
is only “locally” submodular. The closure operator is not monotone but possesses a (relaxed) Steinitz—McLane exchange property.
We define two classes of subsets, called rank-feasible and closure-feasible, so that the rank and closure behave nicely for
them. In particular, restricted to rank-feasible sets the rank function is submodular. Finally we show that Rado’s theorem
on independent transversals of subsets of matroids remains valid for feasible transversals of certain sets of greedoids.
Dedicated to Paul Erdős on his seventieth birthday
Supported by the joint research project “Algorithmic Aspects of Combinatorial Optimization” of the Hungarian Academy of Sciences
(Magyar Tudományos Akadémia) and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 21). |
| |
Keywords: | 05 B 35 68 C 05 15 A 03 |
本文献已被 SpringerLink 等数据库收录! |
|