グリードイド
グリードイド(E,F)が次を満たすとき、強交換性を持つという。
任意の A ∈ F {\displaystyle A\in F} について、Bは A ⊆ B {\displaystyle A\subseteq B} を満たす任意の極大元とする。このとき、 A ∪ { x } ∈ F {\displaystyle A\cup \{x\}\in F} を満たす任意の x ∈ E ∖ B {\displaystyle x\in E\setminus B} に対して、 A ∪ { y } ∈ F {\displaystyle A\cup \{y\}\in F} と ( B ∖ { y } ) ∪ { x } ∈ F {\displaystyle (B\setminus \{y\})\cup \{x\}\in F} を同時に満たす y ∈ B ∖ A {\displaystyle y\in B\setminus A} が存在する。
グリードイド(E,F)が強交換性を持つとき、かつそのときのみ、すべてのモジュラーな重み関数 c : 2 E → R + {\displaystyle c:2^{E}\to \mathbb {R} _{+}} でグリードイドに対する貪欲法は最適解を出力することが知られている。