マトロイド

マトロイド（テンプレート:Lang-en-short）は、ある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。

定義

E = {1, 2, 3} におけるそれぞれの例。左は(A1),(A2),(A3)を満たすからマトロイド。中央は(A1),(A2)を満たすから独立性システム。右は(A1),(A3)を満たすからグリードイド。

有限集合 テンプレート:Mvar とその部分集合族 $F\subseteq 2^E$ の組 テンプレート:Math2 が

• (A1) $\mathrm{\varnothing }\in F$
• (A2) $X\subseteq Y\in F\Rightarrow X\in F$
• (A3) $X,Y\in F,|X|>|Y|\Rightarrow \mathrm{\exists }x\in X\setminus Y\text{ s.t. }Y\cup \{x\}\in F.$

を満たすとき、マトロイドと呼ばれ、(A1) および (A2) のみを満たすとき独立性システム (independence system) と呼ばれる。さらに (A1) および (A3) を満たすときグリードイド (greedoid) と呼ばれる。

以下に本項で使う用語の定義を挙げる。

• 独立集合 (テンプレート:Lang-en-short) - $F$ の要素
• 従属集合 (テンプレート:Lang-en-short) - $2^E\setminus F$ の要素
• サーキット (テンプレート:Lang-en-short) - 極小な従属集合
• 基 (テンプレート:Lang-en-short) - 極大な独立集合
• $X$ の基 - $X\subseteq E$ とする $X$ の部分集合の中で極大な独立集合

ランク、階数関数

独立性システム (E, F) の階数 (rank) 関数 $r:2^E\to ℝ$ は、$X\subseteq E$ に対して

$r(X):=\max \{|Y|:Y\subseteq X,Y\in F\}$

と定義される。マトロイドならば、公理(A3) から テンプレート:Mvar の部分集合 テンプレート:Mvar に対して テンプレート:Mvar のどの基も元数は等しいため、階数関数を$X$の基の大きさと定義しても構わない。

例えば、E = {1, 2, 3}, F={{},{1},{2},{1,2}} というマトロイドならば r({1}) = 1, r({1, 2}) = 2, r({1, 2, 3}) = 2, r({1, 3}) = 1 等となる。

独立性システム $(E,F)$ の階数関数 $r:2^E\to ℝ$ は任意の $X,Y\subseteq E$ と $x,y\in E$ について次の性質を持つ。

• (R1) $r(X)\le |X|$
• (R2) $X\subseteq Y\Rightarrow r(X)\le r(Y)$
• (R3) $r(\mathrm{\varnothing })=0$

さらに、$(E,F)$ がマトロイドならば次の性質も持つ。

• (R4) $r(X\cup Y)+r(X\cap Y)\le r(X)+r(Y)$
• (R5) $r(X)\le r(X\cup \{x\})\le r(X)+1$
• (R6) $r(X\cup \{x\})=r(X\cup \{y\})=r(X)\Rightarrow r(X\cup \{x,y\})=r(X)$

特に(R4)に示されているように、階数関数が劣モジュラであることは、マトロイドの極めて重要な性質である。

閉包

独立性システム $(E,F)$ の閉包 (closure) 関数 $\sigma :2^E\to 2^E$ は、$X\subseteq E$ に対して

$\sigma (X):=\{y\in E:r(X\cup y)=r(X)\}$

で定義される。 $\sigma (X)$ を テンプレート:Mvar の閉包と呼ぶ。

マトロイド $(E,F)$ の閉包関数 $\sigma :2^E\to 2^E$ は次の性質を持つ。

• (L1) 任意の $X\subseteq E$ に対して、$X\subseteq \sigma (X)$
• (L2) 任意の $X,Y\subseteq E$ に対して、$X\subseteq Y\Rightarrow \sigma (X)\subseteq \sigma (Y)$
• (L3) 任意の $X\subseteq E$ に対して、$\sigma (X)=\sigma (\sigma (X))$
• (L4) 任意の $X,Y\subseteq E$ と任意の $x,y\in E$ に対して、$y\in ̸\sigma (X),y\in \sigma (X\cup \{x\})\Rightarrow x\in \sigma (X\cup \{y\})$

ランク商

下方ランク (lower rank) 関数 $\rho (X)$ を $X$ に含まれる基の最小元数とする。つまり、

$\rho (X):=\min \{|Y|:Y\subseteq X,Y\in F$ かつ $\mathrm{\forall }x\in X\setminus Y$ に対し $Y\cup \{x\}\in ̸F\}$

と定義する。すると、ランク商 (rank quotient) は次のように定義される。

$q(E,F):=\underset{X\subseteq E}{\min }\frac{\rho (X)}{r(X)}$

マトロイドのとき $q(E,F)=1$ である。独立性システムのとき $q(E,F)\le 1$ であり、$A\in F,b\in E$ に対して $A\cup \{b\}$ が高々テンプレート:Mvar 個しかサーキットを持たないならば $1/p\le q(E,F)$ であることが知られているのでランク商を見積もることが可能である。

例

一様マトロイド

E を有限集合とし、ある整数 r 以下の要素数を持つ 2テンプレート:Sup の部分集合をFとするとき、(E, F) はマトロイドとなる。これを、テンプレート:仮リンク (uniform matroid) と呼び、n=|E|としたとき $U_n^r$ などと書く。$U_n^r$ における基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの直和はテンプレート:仮リンク (partition matroid) と呼ばれる。具体的には、$B_1,\dots ,B_k$を互いに素な集合とし、それぞれに $0\le d_i\le |B_i|(0\le i\le k)$ を定めたとき、$0\le i\le k$ それぞれにおいて $|I\cap B_i|\le d_i$ を満たす $I\subset \bigcup _i{B}_i$ の集合を F とすれば、マトロイドとなる。

グラフ理論におけるマトロイド

E を無向グラフGの辺集合、F を森の集合とするとき、(E, F) はマトロイドとなり、テンプレート:仮リンク (graphic matroid) または 閉路マトロイド (cycle matroid) と呼ぶ。しばしばグラフGがグラフ的マトロイドであることを M(G) と書く。グラフ的マトロイドにおける従属集合は、閉路を持つグラフの集合であるから、サーキットとは単純閉路となる辺集合である。また（X の）基とは（X の部分集合の中で）できうる最大の森のことで、明らかに（X でカバーされる）点の数 − 1 本の辺で作られる森が最大であり、この森の集合を言う。よって、階数関数は r(X) = (Xがカバーする点数) − 1 と書ける。

他にも、グラフにおけるマトロイドはいくつか知られている。

• E を無向グラフ G の辺集合、F を (G, X) がテンプレート:仮リンクとなるようなXの集合とするとき (E, F) はマトロイドとなる。これを、テンプレート:仮リンク (bicircular matroid) と呼ぶ。
• 点集合 U, V、辺集合 X とする2部グラフ テンプレート:Math2 において、マッチングの端点となる点集合 $S\subseteq U$ を要素とする集合をFとするとき、(U, F) はマトロイドとなる。これを、横断マトロイド (transversal matroid) と呼ぶ。完全2部グラフ $K_{n,r}$ の横断マトロイドは、一様マトロイド $U_n^r$ である。
• 点集合を V とするグラフにおいて、点の部分集合を $V^{\prime },U\subseteq V$ とする。U への点素な |U| 本の道が存在する V' の部分集合を F の要素とすると、(V', F) はマトロイドとなる。これを、テンプレート:仮リンク (gammoid) と呼ぶ。特に、(V, F) を狭義ガンモイド (strict gammoid) と呼ぶ。

線形代数におけるマトロイド

Vámosマトロイドは、網掛け四角の4頂点をサーキット(計5つ)とするマトロイドである。

E を体上の行列の列集合、その体上で線形独立である列の集合を F とするとき、(E, F) はマトロイドとなり、ベクトルマトロイド (vector matroid) と呼ぶ。マトロイドが同等の体 K 上のベクトルマトロイドとして記述できるとき、表現可能であると呼ばれる。任意の体上で表現可能なマトロイドを正則マトロイド (regular matroid) と呼び、位数2の有限体上で表現可能なマトロイドをテンプレート:仮リンク (binary matroid) と呼ぶ。これらは、

• マトロイド ⊃ 2値マトロイド ⊃ 正則マトロイド ⊃ グラフ的マトロイド

という包含関係が成り立つ。一方で、Fanoマトロイドは、2値マトロイドであるが（実数体上では表現できないため）正則マトロイドではない。また、テンプレート:仮リンク (Vámos matroid) は、任意の体上で表現できないマトロイドの最も簡単な例である。

その他のマトロイド

• 2部マトロイド (bipartite matroid) は、サーキットの大きさがすべて偶数であるマトロイドである。2部グラフのグラフ的マトロイドを一般化しており、グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である。
• テンプレート:仮リンク (Sylvester matroid) は、すべてのサーキットの大きさが3であるようなマトロイドである。例えば、ランク2の一様マトロイド $U_n^2$ はシルベスターマトロイドである。
• テンプレート:仮リンク (paving matroid) は、すべてのサーキットの大きさがランクよりも大きいマトロイドである。例えば、一様マトロイド $U_n^r$ のランクはrであり、サーキットの大きさは常に r + 1 であるため、pavingマトロイドである。
• テンプレート:仮リンク(eulerian matroid) は、要素がサーキットによって分割できるようなマトロイドである。例えば、一様マトロイド $U_n^r$ は r + 1 が n を割り切るとき、かつそのときのみオイラーマトロイドである。

他の公理系

集合Eとその部分集合の族Fが(A1)から(A3)を満たすときマトロイドと呼ぶことにし、そこから基やランクを定義した。だが、実はこれらの性質を持つ族あるいは関数からマトロイドとなる F を得ることができる。

基族

有限集合 テンプレート:Mvar と $ℬ\subseteq 2^E$ とする。 $ℬ$ がマトロイド (E, F) の基族であるための必要十分条件は次の(B1),(B2)が成り立つことである。

• (B1) $ℬ\ne \mathrm{\varnothing }$
• (B2) 任意の $B^{\prime },B^{″}\in ℬ,x\in B^{\prime }\setminus B^{″}$ について $(B^{\prime }\setminus \{x\})\cup \{y\}\in ℬ$ となる $y\in B^{″}\setminus B^{\prime }$ が存在する。

基が1つしかない場合は明らかにマトロイドとなる。そうでない場合、例えば $E=\{1,2,3\},ℬ=\{\{1,2\},\{2,3\},\{1,3\}\}$ とすると $ℬ$ は(B1)および(B2)を満たす。このような基の族を持つマトロイドは、一様マトロイド $U_3^2$ ただ1つに決まることが分かる。また、基族が $ℬ=\{\{1,2\},\{3\}\}$ のときは(B2)を満たさないため、この基族ではマトロイドにならない。事実、$F=\{\{1\},\{2\},\{3\},\{1,2\}\}$ とすると、この例の基族となるが、(A3)を満たさずマトロイドになっていない。

サーキットの族

有限集合 E と C ⊆ 2テンプレート:Sup とする。C がマトロイド (E, F) のサーキットの族であるための必要十分条件は次の(C1),(C2),(C3)が成り立つことである。

• (C1) $\mathrm{\varnothing }\in ̸C$
• (C2) 任意の Cテンプレート:Sub, Cテンプレート:Sub ∈ C について Cテンプレート:Sub ⊆ Cテンプレート:Sub ならば Cテンプレート:Sub = Cテンプレート:Sub である。
• (C3) 任意の Cテンプレート:Sub, Cテンプレート:Sub ∈ C は Cテンプレート:Sub ≠ Cテンプレート:Sub で c ∈ Cテンプレート:Sub ∩ Cテンプレート:Sub とするとき、$C_3\subseteq (C_1\cup C_2)\setminus \{c\}$ となる Cテンプレート:Sub ∈ C が存在する。

ランク関数

マトロイドのランク関数は(R1)から(R6)を満たすが、逆にEと(R1),(R2),(R4)を満たす関数 $r:2^E\to {\mathbb{Z}}_{+}$ を与えればFは直ちに決まり (E, F) はマトロイドであり、r はランク関数である。

例えば、E = {1, 2, 3} とし、関数 r を

$r(\mathrm{\varnothing })=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$

と定義すると、r は(R1),(R2),(R4)を満たすことが確認できる。すると、r(X) = |X| となる X の族を F と定義すると F = {{1}, {3}, {1,3}} となり、(E, F) はマトロイドになることが確認できる。このように、r を決めれば対応する F がただ1つに決まる。

閉包関数

(L1)から(L4)を満たす関数 $\sigma :2^E\to 2^E$ はマトロイドの閉包関数となる。

マトロイドの構成法

ここでは、1つ以上のマトロイド（あるいは独立性システム）から新たなマトロイドを構成する方法について説明する。

双対

独立性システム (E, F) に対して、Fテンプレート:Sup を $X\cap B=\mathrm{\varnothing }$ となる (E, F) の基 B が存在する $X\subseteq E$ の集合とする。このとき、(E, Fテンプレート:Sup) を (E,F) の双対 (dual) と定義する。

双対には次のような性質がある。

• (E, Fテンプレート:Sup) = (E,F)
• (E, F) が独立性システムならば、(E, Fテンプレート:Sup) は独立性システム
• (E, F) はマトロイド $⟺$ (E, Fテンプレート:Sup) はマトロイド。
• マトロイド (E, F) とその双対 (E, Fテンプレート:Sup) とし、それぞれのランク関数を r, rテンプレート:Sup とすると、rテンプレート:Sup は任意の X ⊆ E に対して $r^{*}(X)=|X|+r(E\setminus X)-r(E)$ である。

例えば、 E = {1, 2, 3}, F = {{1}, {2}, {1,2}} というマトロイドに対して基の族 B = { {1, 2} } だから Fテンプレート:Sup = { {3} } となる。双対のランク関数も、例えば rテンプレート:Sup({1, 3}) = 2 + r({2}) - r({1, 2, 3}) = 2 + 1 - 2 = 1 となるように、成り立っていることが分かる。

また、平面グラフに対する双対とグラフ的マトロイドの双対の概念は一致する。つまり、任意の平面的グラフ G の閉路マトロイド M(G) の双対は、G の双対平面グラフ Gテンプレート:Sup のマトロイドと（平面埋め込みの方法によらず）同一である。

交差

2つの独立性システム (E, Fテンプレート:Sub), (E, Fテンプレート:Sub) とするとき、(E, Fテンプレート:Sub ∩ Fテンプレート:Sub) を2つの独立性システムの交差 (intersection) と定義する。有限個の独立性システムの交差も同様に定義でき、交差もまた独立性システムとなる。任意の独立性システム (E, F) は、有限個のマトロイドの交差で表せる。さらに、p 個のマトロイドの交差ならば、q(E, F) ≧ 1/p。

例えば2部グラフのマッチング問題の場合、Eを辺集合、Fをマッチング集合とすれば、2部グラフであるから点集合は A ∪ B と書ける。Fテンプレート:Sub を任意の点 a ∈ A に繋がる辺は高々1本であるという条件とするならば (E, Fテンプレート:Sub) はマトロイドであり、同様に Fテンプレート:Sub を任意の点 b ∈ B に繋がる辺は高々1本であるという条件とするならば (E, Fテンプレート:Sub) もマトロイドである。F = Fテンプレート:Sub ∩ Fテンプレート:Sub なので、(E, F) は2つのマトロイド (E, Fテンプレート:Sub), (E, Fテンプレート:Sub) の交差である。

合併

2つのマトロイド (E, Fテンプレート:Sub),(E, Fテンプレート:Sub) とする。Xテンプレート:Sub ∈ Fテンプレート:Sub, Xテンプレート:Sub ∈ Fテンプレート:Sub となる X の分割 X = Xテンプレート:Sub ∪ Xテンプレート:Sub が存在するとき、X ⊆ E は 分割可能 (partitionable) であると呼ぶ。$F=\{X\subseteq E:X\text{ is partitionable}\}$ とするとき、(E, F) を (E, Fテンプレート:Sub), (E, Fテンプレート:Sub) の合併(union) あるいは和(sum) と呼ぶ。有限個のマトロイドの合併も同様に定義できる。

• マトロイドの合併は、マトロイドとなる。
• k個のマトロイド (E, Fテンプレート:Sub), …, (E, Fテンプレート:Sub) の各ランク関数を rテンプレート:Sub, …, rテンプレート:Sub とすると、これらの合併 (E, F) のランク関数は $r(X)=\underset{A\subseteq X}{\min }(|X\setminus A|+\sum _{i=1}^k{r}_i(A))$ である。

組合せ最適化

組合せ最適化問題の多くは、独立性システム $(E,F)$ とコスト関数 $c:E\to ℝ$ に対して、$\sum _{e\in X}c(e)$ を最大（あるいは最小）にする $X\in F$ を求める最適化問題に定式化できる。

例えば、以下の中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。

• 巡回セールスマン問題 - Eをグラフの辺、Fはハミルトン閉路の部分集合
• ナップサック問題 - Eを荷物、Fは規定の重さを超えない荷物の組合せ
• 最小全域木問題 - Eはグラフの辺、Fはグラフの森の集合

貪欲法

マトロイドにおいては貪欲法で最適解が得られることを示す。なお、マトロイドの貪欲法は組合せ最適化の貪欲法の全てを網羅しているわけではない。たとえば、クラスカル法はマトロイド上の貪欲法で説明できるが、プリム法やダイクストラ法は異なる。

最良選択貪欲法

最良選択貪欲法は、$c(e)$ の大きい順に $e\in E$ を暫定解に追加できるならば追加し追加できない場合は次の要素に移ることを繰り返すアルゴリズムである。つまり、

1. $c(e_1)\ge c(e_2)\ge \cdots \ge c(e_n)$ となるように $E=\{e_1,e_2,\cdots ,e_n\}$ をソートする。
2. $E_{ans}\leftarrow \mathrm{\varnothing }$
3. For i = 1 to n : $E_{ans}\cup \{e_i\}\in F$ ならば $E_{ans}\leftarrow E_{ans}\cup \{e_i\}$
4. $E_{ans}$を解として出力する。

というアルゴリズムである。

最良選択貪欲法で得られる解のコストを $c(G)$、最適解のコストを $c(OPT)$ とすると、ランク商 $q(E,F)$ を使って

$q(E,F)\le \frac{c(G)}{c(OPT)}\le 1$

が任意のコスト関数に対して成立する。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム (E, F) がマトロイドであるための必要十分条件は最良選択貪欲法で全ての $c:E\to {ℝ}_{+}$ に対して最大化問題の最適解を求めることができることである。これを Edmonds-Rado 定理という。

証明の概要

$c(G)\ge q(E,F)c(OPT)$ の証明の概要を述べる。

テンプレート:Mvar を最良選択貪欲法で得られる解、$OPT$ を最適解とする。$E=\{e_1,\dots ,e_n\}$ は、$c(e_1)\ge c(e_2)\ge \cdots \ge c(e_n)$ となるようにソート済みであるとし、$E_j=\{e_1,\dots ,e_j\}$ とする。また、

$d_j=\{\begin{array}{cc}c(e_n),& \text{if }j=n\\ c(e_j)-c(e_{j+1}),& \text{otherwise}\end{array}$

とし、任意の $X\subseteq 2^E$ に対して、$X_j=X\cap E_j$ と置く。このとき、次の事実が成り立つ。

• 任意の $X\subseteq 2^E$ において、$c(X)=\sum _{j=1}^n|X_j|d_j$
• 任意の $1\le j\le n$ において、$\rho (E_j)\le |G_j|$
• 任意の $X\subseteq E$ において、$r(X)q(E,F)\le \rho (X)$
• 任意の $1\le j\le n$ において、$|OP{T}_j|\le r(E_j)$

以上のことから、

$c(G)=\sum _{j=1}^n|G_j|d_j\ge \sum _{j=1}^n\rho (E_j)d_j\ge q(E,F)\sum _{j=1}^{n}r(E_j)d_j\ge q(E,F)\sum _{j=1}^n|OP{T}_j|d_j=q(E,F)c(OPT)$

となる。

最悪棄却貪欲法

独立性システム (E, F) とコスト関数 $c:E\to {ℝ}_{+}$に対する最小化問題を解く。最悪棄却貪欲法は、都合の悪い e ∈ E を優先して解から除外する。つまり、

1. $c(e_1)\ge c(e_2)\ge \cdots \ge c(e_n)$ となるように $E=\{e_1,e_2,\cdots ,e_n\}$ をソートする。
2. $E_{ans}\leftarrow E$
3. For i = 1 to n : $E_{ans}\setminus \{e_i\}$ が基を含むならば、$E_{ans}\leftarrow E_{ans}\setminus \{e_i\}$
4. $E_{ans}$ を解として出力する。

というアルゴリズムである。

最悪棄却貪欲法で得られる解のコストを c(G)、最適解のコストを c(OPT) とすると、ランク商 q(E, F)、双対な独立性システム (E, Fテンプレート:Sup) の下方ランク関数 ρテンプレート:Sup、ランク関数 rテンプレート:Sup を使って

$1\le \frac{c(G)}{c(OPT)}\le \underset{X\subseteq E}{\max }\frac{|X|-{\rho }^{*}(X)}{|X|-r^{*}(X)}$

と書ける。マトロイドならば ρテンプレート:Sup = rテンプレート:Sup なので、常に最適解を得られることが分かる。

オラクル

組合せ最適化問題において F は明示的に与えられることはまずない。F を列挙しようとすることは無謀であるので、現実には E とコスト関数cのみが与えられる。最良選択貪欲法を実行するには、さらに独立性オラクルを必要となる。独立性オラクルとは、X ⊆ E が与えられたとき X ∈ F であるかどうかを判定するオラクルである。これがないと最良選択貪欲法の3番目のステップは実行できない。同様に最悪棄却貪欲法を実行するためには X ⊆ E が与えられたとき X が基を含むかを判定する基拡張集合オラクルを必要とする。

では、独立性オラクルか基拡張集合オラクルどちらか一方が与えられたとき、そのオラクルを使ってもう一方を多項式時間で実行可能(多項式等価)だろうか。例えば、巡回セールスマン問題に対する独立性システムの独立性オラクルはつまり、与えられた辺集合がハミルトン閉路の部分集合であるかを判定するものであるが、グラフは完全グラフであるので、多項式時間で実行可能である。対して基拡張集合オラクルは与えられた辺集合からいくらか辺を削除することによってハミルトン閉路になるかということを判定しなくてはならない。それはつまりハミルトン閉路問題と等価であり、ハミルトン閉路問題はNP完全であるため難しいと言える。このように、独立性システムにおいて独立性オラクルと基拡張集合オラクルは必ずしも多項式等価ではない。

マトロイドにおいては独立性オラクル、基拡張集合オラクル、ランク関数を返すランクオラクル、閉包関数を返す閉包オラクル全て多項式等価である。しかし、与えられた部分集合が基かどうかを判定する基決定オラクルは独立性オラクルより弱いし、与えられた部分集合の最小元数の従属部分集合を返すオラクルは独立性オラクルより強い。

近似

最適化問題は厳密解を求めることが現実的でないことが多いために、近似の限界についても研究されている。次の問題が効率的に解ける（入力のサイズと 1/ε の多項式時間で解を出力するアルゴリズムが存在する）ことと、誤差が高々 1+ε 倍の解を出力する多項式時間アルゴリズムが存在することは同値である。

独立性システム (E, F)、コスト関数 $c:E\to {\mathbb{Z}}_{+}$、部分集合 S, S' ⊆ E, ε > 0 が

$\frac{1}{1+ϵ}c(S)\le c(S^{\prime })\le (1+ϵ)c(S)$

であるとき、S ⊆ B となる基 B が存在して S' ⊆ B' となる基 B' 全てに対して (1 + ε)c(B) ≧ c(B') が成立するか？

つまり、部分的なコスト（c(S) や c(S')）が高々 1 + ε 倍違う程度ならば、それらからできうる最適解も 1 + ε 倍程度しか違わないだろうか、という問題である。部分が最適ならば全体も最適であるという場合はε=0であり、よく知られているように動的計画法が存在する。よって、(E, F) をマトロイドに限定するならば多項式時間アルゴリズムは存在する。

ナップサック問題はこのアルゴリズムが知られている珍しい例で、計算時間が $O(n^2\cdot \frac{1}{ϵ})$や $O(n\log (\frac{1}{ϵ})+\frac{1}{{ϵ}^4})$で、出力される解の評価が最適解の評価の高々 1 + ε 倍であるアルゴリズムがある。

マトロイドに関する問題

マトロイド交差問題と分割問題

マトロイド交差問題 (Matroid Intersection Problem) は、2つのマトロイド (E, Fテンプレート:Sub), (E, Fテンプレート:Sub) が与えられたとき、|F| が最大となるような F ∈ Fテンプレート:Sub ∩ Fテンプレート:Sub を求める問題である。マトロイド交差問題は多項式時間で解ける。また、3つ以上のマトロイド交差問題も同様に考えることができるが、これはNP困難問題である。

重み付き版についてもアルゴリズムが知られていて、2つの独立性オラクルの計算量の大きい方を α とすると O(|E|テンプレート:Supα) で解ける。

マトロイド分割問題 (Matroid Partitioning Problem) は k 個のマトロイド (E, Fテンプレート:Sub), …, (E, Fテンプレート:Sub) が与えられたとき |X| が最大になるような分割可能な X ⊆ E を求める問題である。マトロイド交差問題とマトロイド分割問題は等価である。

一般化

グリードイドはマトロイドと反マトロイドを一般化したものである。グリードイドにも貪欲法が定式化できて、特殊な条件下においては最適解を出力する。だが、グリードイド上での最適化問題はNP困難であることが知られている。

また、マトロイドのランク関数が劣モジュラ関数であることは既に述べたが、有限集合Eと劣モジュラ関数 $f:2^E\to {ℝ}_{+}$を用いてポリマトロイド (polymatroid) と呼ばれる有界多面体を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できる。劣モジュラ関数最小化問題は例えばフローネットワークにおける無向グラフの最小カットを求める問題などを一般化している。劣モジュラ関数最小化問題は楕円体法を用いることで多項式時間で解けることが知られて以来、Schrijverのアルゴリズム等が知られている。

参考文献

1. テンプレート:Cite book

関連項目

分野

• 組合せ最適化
• グラフ理論
• 計算複雑性理論

数学的対象

• ポリマトロイド
• グリードイド
• 劣モジュラ関数

外部リンク

• テンプレート:高校数学の美しい物語