マトロイド
E a n s {\displaystyle E_{ans}} を解として出力する。
というアルゴリズムである。
最良選択貪欲法で得られる解のコストを c ( G ) {\displaystyle c(G)} 、最適解のコストを c ( O P T ) {\displaystyle c(OPT)} とすると、ランク商 q ( E , F ) {\displaystyle q(E,F)} を使って
q ( E , F ) ≤ c ( G ) c ( O P T ) ≤ 1 {\displaystyle q(E,F)\leq {\frac {c(G)}{c(OPT)}}\leq 1}
が任意のコスト関数に対して成立する。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム (E, F) がマトロイドであるための必要十分条件は最良選択貪欲法で全ての c : E → R + {\displaystyle c:E\to \mathbb {R} _{+}} に対して最大化問題の最適解を求めることができることである。これを Edmonds-Rado 定理という。
グリードイドはマトロイドと反マトロイドを一般化したものである。グリードイドにも貪欲法が定式化できて、特殊な条件下においては最適解を出力する。だが、グリードイド上での最適化問題はNP困難であることが知られている。
また、マトロイドのランク関数が劣モジュラ関数であることは既に述べたが、有限集合Eと劣モジュラ関数 f : 2 E → R + {\displaystyle f:2^{E}\to \mathbb {R} _{+}} を用いてポリマトロイド (polymatroid) と呼ばれる有界多面体を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できる。劣モジュラ関数最小化問題は例えばフローネットワークにおける無向グラフの最小カットを求める問題などを一般化している。劣モジュラ関数最小化問題は楕円体法を用いることで多項式時間で解けることが知られて以来、Schrijverのアルゴリズム等が知られている。
を満たすとき、マトロイドと呼ばれ、(A1) および (A2) のみを満たすとき独立性システム (independence system) と呼ばれる。さらに (A1) および (A3) を満たすときグリードイド (greedoid) と呼ばれる。
以下に本項で使う用語の定義を挙げる。
独立集合 (英: independent set) - F {\displaystyle F} の要素
従属集合 (英: dependent set) - 2 E ∖ F {\displaystyle 2^{E}\setminus F} の要素
サーキット (英: circuit) - 極小な従属集合
基 (英: base, basis) - 極大な独立集合
X {\displaystyle X} の基 - X ⊆ E {\displaystyle X\subseteq E} とする X {\displaystyle X} の部分集合の中で極大な独立集合
2部マトロイド (bipartite matroid) は、サーキットの大きさがすべて偶数であるマトロイドである。2部グラフのグラフ的マトロイドを一般化しており、グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である。
シルベスターマトロイド(英語版) (Sylvester matroid) は、すべてのサーキットの大きさが3であるようなマトロイドである。例えば、ランク2の一様マトロイド U n 2 {\displaystyle U_{n}^{2}} はシルベスターマトロイドである。
pavingマトロイド(英語版) (paving matroid) は、すべてのサーキットの大きさがランクよりも大きいマトロイドである。例えば、一様マトロイド U n r {\displaystyle U_{n}^{r}} のランクはrであり、サーキットの大きさは常に r + 1 であるため、pavingマトロイドである。
オイラーマトロイド(英語版)(eulerian matroid) は、要素がサーキットによって分割できるようなマトロイドである。例えば、一様マトロイド U n r {\displaystyle U_{n}^{r}} は r + 1 が n を割り切るとき、かつそのときのみオイラーマトロイドである。
任意の 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} において、 | O P T j | ≤ r ( E j ) {\displaystyle |OPT_{j}|\leq r(E_{j})}
以上のことから、
c ( G ) = ∑ j = 1 n | G j | d j ≥ ∑ j = 1 n ρ ( E j ) d j ≥ q ( E , F ) ∑ j = 1 n r ( E j ) d j ≥ q ( E , F ) ∑ j = 1 n | O P T j | d j = q ( E , F ) c ( O P T ) {\displaystyle c(G)=\sum _{j=1}^{n}|G_{j}|d_{j}\geq \sum _{j=1}^{n}\rho (E_{j})d_{j}\geq q(E,F)\sum _{j=1}^{n}r(E_{j})d_{j}\geq q(E,F)\sum _{j=1}^{n}|OPT_{j}|d_{j}=q(E,F)c(OPT)}
となる。