GREEDY STRUCTURE FOR LINEAR OBJECTIVE FUNCTIONS

In [1] Edmonds showed that for any linear objective function a basis of an independent system obtained by greedy algorithm is always a maximum iff the independent system satisfies Steinitz exchange axiom. Such a system is called a matroid.

线性目标函数下的greedy-结构

<正> 有限集合E的一个子集类■2~E,如果对任意的 Y∈■及 X■Y,总有 X∈■,我们则称(E,■)为一独立系统.1971年 J.Edmonds 指出,独立系统(E,■)对任意线性目标函数其greedy基恒为最优基的充分必要条件是■满足交换公理,即对任意的 X,Y∈■,及|Y|>|X|,则存在 y∈Y\X,使 X∪{y}∈■.这时(E,■)是一拟阵.