マトロイド
マトロイドのランク関数は(R1)から(R6)を満たすが、逆にEと(R1),(R2),(R4)を満たす関数 r : 2 E → Z + {\displaystyle r:2^{E}\to \mathbb {Z} _{+}} を与えればFは直ちに決まり (E, F) はマトロイドであり、r はランク関数である。
例えば、E = {1, 2, 3} とし、関数 r を
r ( ∅ ) = 0 , r ( 1 ) = 1 , r ( 2 ) = 0 , r ( 3 ) = 1 , r ( 1 , 2 ) = 1 , r ( 2 , 3 ) = 1 , {\displaystyle r(\emptyset )=0,r({1})=1,r({2})=0,r({3})=1,r({1,2})=1,r({2,3})=1,}
r ( 1 , 3 ) = 2 , r ( 1 , 2 , 3 ) = 2 {\displaystyle \ r({1,3})=2,r({1,2,3})=2\ }
と定義すると、r は(R1),(R2),(R4)を満たすことが確認できる。すると、r(X) = |X| となる X の族を F と定義すると F = {{1}, {3}, {1,3}} となり、(E, F) はマトロイドになることが確認できる。このように、r を決めれば対応する F がただ1つに決まる。
つまり、部分的なコスト(c(S) や c(S'))が高々 1 + ε 倍違う程度ならば、それらからできうる最適解も 1 + ε 倍程度しか違わないだろうか、という問題である。部分が最適ならば全体も最適であるという場合はε=0であり、よく知られているように動的計画法が存在する。よって、(E, F) をマトロイドに限定するならば多項式時間アルゴリズムは存在する。
ナップサック問題はこのアルゴリズムが知られている珍しい例で、計算時間が O ( n 2 ⋅ 1 ε ) {\displaystyle O(n^{2}\cdot {\frac {1}{\epsilon }})} や O ( n log  ( 1 ε ) + 1 ε 4 ) {\displaystyle O(n\log({\frac {1}{\epsilon }})+{\frac {1}{\epsilon ^{4}}})} で、出力される解の評価が最適解の評価の高々 1 + ε 倍であるアルゴリズムがある。
E を有限集合とし、ある整数 r 以下の要素数を持つ 2 の部分集合をFとするとき、(E, F) はマトロイドとなる。これを、一様マトロイド(英語版) (uniform matroid) と呼び、n=|E|としたとき U n r {\displaystyle U_{n}^{r}} などと書く。 U n r {\displaystyle U_{n}^{r}} における基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの直和は分割マトロイド(英語版) (partition matroid) と呼ばれる。具体的には、 B 1 , ... , B k {\displaystyle B_{1},\ldots ,B_{k}} を互いに素な集合とし、それぞれに 0 ≤ d i ≤ | B i | ( 0 ≤ i ≤ k ) {\displaystyle 0\leq d_{i}\leq |B_{i}|\ (0\leq i\leq k)} を定めたとき、 0 ≤ i ≤ k {\displaystyle 0\leq i\leq k} それぞれにおいて | I ∩ B i | ≤ d i {\displaystyle |I\cap B_{i}|\leq d_{i}} を満たす I ⊂ ⋃ i B i {\displaystyle I\subset \bigcup _{i}B_{i}} の集合を F とすれば、マトロイドとなる。
(L2) 任意の X , Y ⊆ E {\displaystyle X,Y\subseteq E} に対して、 X ⊆ Y ⇒ σ ( X ) ⊆ σ ( Y ) {\displaystyle X\subseteq Y\Rightarrow \sigma (X)\subseteq \sigma (Y)}
(L3) 任意の X ⊆ E {\displaystyle X\subseteq E} に対して、 σ ( X ) = σ ( σ ( X ) ) {\displaystyle \sigma (X)=\sigma (\sigma (X))}
(L4) 任意の X , Y ⊆ E {\displaystyle X,Y\subseteq E} と任意の x , y ∈ E {\displaystyle x,y\in E} に対して、 y ∉ σ ( X ) , y ∈ σ ( X ∪ { x } ) ⇒ x ∈ σ ( X ∪ { y } ) {\displaystyle y\not \in \sigma (X),\ y\in \sigma (X\cup \{x\})\Rightarrow x\in \sigma (X\cup \{y\})}
2つのマトロイド (E, F1),(E, F2) とする。X1 ∈ F1, X2 ∈ F2 となる X の分割 X = X1 ∪ X2 が存在するとき、X ⊆ E は 分割可能 (partitionable) であると呼ぶ。 F = { X ⊆ E : X is partitionable } {\displaystyle F=\{X\subseteq E:X{\mbox{ is partitionable}}\}} とするとき、(E, F) を (E, F1), (E, F2) の合併(union) あるいは和(sum) と呼ぶ。有限個のマトロイドの合併も同様に定義できる。
マトロイドの合併は、マトロイドとなる。
k個のマトロイド (E, F1), ..., (E, Fk) の各ランク関数を r1, ..., rk とすると、これらの合併 (E, F) のランク関数は r ( X ) = min A ⊆ X ( | X ∖ A | + ∑ i = 1 k r i ( A ) ) {\displaystyle r(X)=\min _{A{\subseteq }X}(|X\setminus {A}|+\sum _{i=1}^{k}r_{i}(A))} である。