マトロイド
ここでは、1つ以上のマトロイド(あるいは独立性システム)から新たなマトロイドを構成する方法について説明する。
最適化問題は厳密解を求めることが現実的でないことが多いために、近似の限界についても研究されている。次の問題が効率的に解ける(入力のサイズと 1/ε の多項式時間で解を出力するアルゴリズムが存在する)ことと、誤差が高々 1+ε 倍の解を出力する多項式時間アルゴリズムが存在することは同値である。
独立性システム (E, F)、コスト関数 c : E → Z + {\displaystyle c:E\to \mathbb {Z} _{+}} 、部分集合 S, S' ⊆ E, ε > 0 が
1 1 + ε c ( S ) ≤ c ( S ′ ) ≤ ( 1 + ε ) c ( S ) {\displaystyle {\frac {1}{1+\epsilon }}c(S)\leq c(S')\leq (1+\epsilon )c(S)}
であるとき、S ⊆ B となる基 B が存在して S' ⊆ B' となる基 B' 全てに対して (1 + ε)c(B) ≧ c(B') が成立するか?
マトロイド(英: matroid)は、ある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。