Жадный алгоритм Радо — Эдмондса

${\displaystyle X}$— носитель матроида, ${\displaystyle I}$ — семейство независимых множеств.

Для всех ${\displaystyle i}$ от ${\displaystyle 0}$ до ранга матроида строится множество ${\displaystyle A_{i}\in I}$ мощности ${\displaystyle i}$, вес которого является минимальным среди весов независимых подмножеств той же мощности.

${\displaystyle A_{0}=\varnothing }$ — очевидно.

Строятся эти множества так: ${\displaystyle A_{i+1}=A_{i}+\left\{x\right\}}$, где ${\displaystyle x}$ — минимальный из элементов ${\displaystyle y\in X\setminus A_{i}}$ таких, что ${\displaystyle A_{i}\cup \left\{y\right\}\in I}$.

Ответ задачи — ${\displaystyle A_{n}}$, где ${\displaystyle n}$ — ранг матроида.

Алгоритм Радо—Эдмондса обобщает жадные алгоритмы. Например, будучи применённым к графическому матроиду, он превращается в алгоритм Краскала поиска остовного леса минимального веса.