マトロイド

提供: miniwiki
2018/8/19/ (日) 17:18時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

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

定義

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

有限集合 [math]E[/math] とその部分集合族 [math]F \subseteq 2^E[/math] の組 [math](E, F)[/math] について[注 1]

  • (A1) [math]\emptyset\in{F}[/math]
  • (A2) [math]X \subseteq Y \in F[/math] ならば [math]X \in F[/math]
  • (A3)X,Y∈F,|X|>|Y|ならば[math]Y\cup\{x\}\in{F}[/math]となる[math]x{\in}X\setminus{Y}[/math]が存在する。

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

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

  • 独立集合 (: independent set) - [math]F[/math] の要素
  • 従属集合 (: dependent set) - [math]2^E \setminus F[/math] の要素
  • サーキット (: circuit) - 極小な従属集合
  • (: base, basis) - 極大な独立集合
  • Xの - [math]X \subseteq E[/math] とする [math]X[/math] の部分集合の中で極大な独立集合
ファイル:Hamiltonian not matroid example.svg
Xを赤い辺、Yを青い辺とする。それぞれは明らかにハミルトン閉路の部分集合である。[math]|X|=8\gt 6=|Y|[/math]だが、赤い辺のいずれを青い辺に加えても、枝分かれしてしまうのでハミルトン閉路の部分集合にはなり得ない。よって、「Fはハミルトン閉路の部分集合」という条件では(A3)を満たさない。

マトロイド及び独立性システムの定義を与えたが、ひどく抽象的で理解しづらいかもしれない。ここでは具体的なモデルとしてグラフで考えよう。Eを辺の集合とする。Fは辺の任意の組合せの中で(A2)の条件を満たすものでなくてはならない。そのために「Fは集合」や「Fはハミルトン閉路の部分集合」という条件を与える。これらはいずれも(A2)を満たす。なぜならば、森から辺を取り去っても森であるし、ハミルトン閉路の部分集合から辺を取り去ってもハミルトン閉路の部分集合だからである。しかし「Fはハミルトン閉路の部分集合」という条件では図に示すように(A3)を満たさない。対して「Fは森集合」は(A3)を満たすから、Eをグラフの辺集合、Fを森集合とする組(E,F)はマトロイドであるということが言える。

Fを森集合とした場合、従属集合は閉路を持つグラフの集合であるから、サーキットとは単純閉路となっている辺集合である。また(Xの)基とは(Xの部分集合の中で)できうる最大の森のことで、明らかに(Xでカバーされる)点の数-1本の辺で作られる森が最大であり、この森の集合を言う。

Eをグラフの辺集合、Fを森集合とする(E,F)はマトロイドになることは上述したが、それも含めて次のような場合もマトロイドになって特別に名前が与えられている。

ベクトルマトロイド (vector matroid)
Eは上の行列Cの列集合で、Fの元に含まれる列集合はその体上で線形独立である。
体を理解しなくても、その部分を実数と読み替えれば線形代数でよく知られた事実よりマトロイドであることが分かる。本項ではベクトルマトロイドと捉えて解説することはないが、マトロイドという名前が行列(matrix)によるという事実を見ても分かるとおり、歴史上は行列の線形独立性から発展した概念である。
閉路マトロイド (cycle matroid)
Eは無向グラフGの辺集合であり、Fは閉路のない辺集合(森)の族。しばしばグラフGが閉路マトロイドであることをM(G)と書く。
グラフ的マトロイド (graphic matroid)
(E,F)はマトロイドであり、閉路マトロイドと同型であるときグラフ的マトロイドと呼ぶ。つまり、EとFの定義はどうであれ(たとえグラフと関係なさそうに見えても)、閉路マトロイドと同一視できるものを言う。例えば、E={1,2,3},F={f⊆E2,|f|≦2}は3つの辺を持つグラフの閉路マトロイドと同一視できるからグラフ的マトロイドであると言える。なお、これは次に紹介する一様マトロイドの例でもある。
一様マトロイド (uniform matroid)
Eは有限集合とし、ある整数k以下の元数を持つ2Eの部分集合。明らかに基は元数がkであるようなEの部分集合である。

ランク、階数関数

独立性システム (E,F) の階数 (rank) 関数 [math]r: 2^E \to \mathbb{R}[/math] は、X⊆Eに対して

[math]r(X) = \max \{ |Y| \mid Y \subseteq X,Y \in F \}[/math]

と定義される。グラフで考えれば F が森集合ならば、X から作れる最大の森の辺数であるから、カバーしている点の個数に依存するので |Y| はどんな Y⊆X,Y∈F についても一定である。この事実は(A3)からも明らかであり、一般にマトロイドの場合はEの部分集合Xに対してXのどの基も元数は等しい。つまり、マトロイドならば階数関数をr(X)={|Y|:Y⊆X,Y∈F}としても構わない。

独立性システム [math](E,F)[/math] の階数関数 [math]r: 2^E \to \mathbb{R}[/math] は任意のX,Y⊆Eとx,y∈Eについて次の性質を持つ。

  • (R1) [math]r(X) \leq |X|[/math]
  • (R2) [math]X \subseteq Y[/math]ならば [math]r(X) \leq r(Y)[/math]である。
  • (R3) [math]r(\emptyset)=0[/math]

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

  • (R4) [math]r(X \cup Y)+r(X \cap Y) \leq r(X) + r(Y)[/math]
  • (R5) [math]r(X) \leq r(X \cup \{x\}) \leq r(X)+1[/math]
  • (R6) [math]r(X \cup \{x\}) = r(X \cup \{y\}) = r(X)[/math] ならば [math]r(X \cup \{x,y\}) = r(X)[/math]

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

いくつかの例を挙げよう。前述した通り閉路マトロイドにおいてXの基の元数はXがカバーする点の数より1小さいからr(X)=(Xがカバーする点数)-1と書ける。また、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等となる。

閉包

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

[math] \sigma (X) = \{ y \in E \mid r(X \cup {y}) = r(X) \} [/math]

で定義される。 [math]\sigma(X)[/math][math]X[/math] の閉包と呼ぶ。

マトロイド [math](E,\mathcal{F})[/math] の閉包関数 [math]\sigma: 2^E \to 2^E[/math] は次の性質を持つ。

  • (L1) 任意の [math]X \subseteq E[/math] に対して、 [math] X \subseteq \sigma(X)[/math]
  • (L2) 任意の [math]X, Y \subseteq E[/math] に対して、 [math] X \subseteq Y[/math] ならば [math] \sigma(X) \subseteq \sigma(Y)[/math]
  • (L3) 任意の [math]X \subseteq E[/math] に対して、 [math] \sigma(X) = \sigma(\sigma(X))[/math]
  • (L4) 任意の [math] X, Y \subseteq E[/math] と任意の [math] x,y \in E[/math] に対して、 [math] y \not\in \sigma(X), y \in\sigma(X\cup\{x\})[/math] ならば [math] x \in \sigma(X \cup \{y\}) [/math]

ランク商

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

[math]\rho(X) = \min \{ |Y|:Y \subseteq X, Y \in F[/math] かつ [math]\forall{x} \in X \setminus Y[/math] に対し [math]Y \cup \{x\} \not\in F \}[/math]

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

[math]q(E,F)=\min_{F\subseteq{E}}\frac{\rho(F)}{r(F)}[/math]

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

これにより、Eを辺集合、Fをマッチンググラフ集合とすると、q(E,F)≧1/2が得られる。これは、適当な辺を追加してできるのは高々長さ3のパスであるから、サーキットは2個しかできないのである。しかし、Eを点集合、Fを安定集合とするとq(E,F)はいくらでも小さくなる。なぜならば、スターグラフ(ネットワーク構成のスター型のようなグラフ)において、周囲の点を選べばそれは安定集合となるので、b∈Eとして中心の点を与えればサーキットは周囲の点の個数個になり、周囲の点数を無限に増やすことによってサーキットをいくらでも多くできるからである。また、マトロイドの場合q(E,F)=1であるので、任意のb∈Eを加えてもサーキットは高々1個しか持たない。例えば、Eを辺集合、Fを森集合とすると、森にどんな辺を加えても閉路は高々1個しか作れない。

他の公理系

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

基族

有限集合 [math]E[/math][math]\mathcal{B} \subseteq 2^E[/math] とする。 [math]\mathcal{B}[/math] がマトロイド (E,F) の基族であるための必要十分条件は次の(B1),(B2)が成り立つことである。

  • (B1) [math]B\neq\emptyset[/math]
  • (B2) 任意の[math]B',B''\in \mathcal{B}, x \in B' \setminus B''[/math] について [math](B'\setminus \{ x \}) \cup \{ y \} \in \mathcal{B}[/math] となる [math]y \in {B''} \setminus {B'}[/math] が存在する。

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

サーキットの族

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

  • (C1) [math]\emptyset\not\in{C}[/math]
  • (C2) 任意のC1,C2∈C について C1⊆C2 ならば C1=C2 である。
  • (C3) 任意の C1,C2∈C は C1≠C2 で c∈C1∩C2 とするとき、[math]C_3 \subseteq (C_1 \cup C_2) \setminus \{c \}[/math] となる C3∈C が存在する。

ランク関数

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

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

[math]r(\emptyset)=0,r({1})=1,r({2})=0,r({3})=1,r({1,2})=1,r({2,3})=1,[/math]
[math]\ r({1,3})=2,r({1,2,3})=2\ [/math]

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

閉包関数

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

双対性

ファイル:Independence sysytem dual.svg
E={1,2,3}における双対の例。左上はマトロイドなのでその双対である右上もマトロイドである。左下は独立性システムなのでその双対である右下も独立性システムである。

独立性システム (E,F) の双対 (dual) は (E,F*) である。ただし F* の要素 f は E の部分集合であって、[math]f{\cap}b=\emptyset[/math] となる (E,F) の基 b が存在する。 (E,F**)=(E,F) であり、 (E,F) がマトロイドであることと (E,F*) はマトロイドであることは等価である[2]。マトロイド(E,F)とその双対(E,F*)とし、それぞれのランク関数をr,r*とすると、r*は任意のX⊆Eに対して

[math]r^*(X)=|X|+r(E{\setminus}X)-r(E)[/math]

である。

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

グラフの双対

双対」を参照すれば分かるとおり、数学における双対の概念は多方面にわたっている。実は、平面グラフに対する双対と閉路マトロイドの双対の概念は一致する。つまり、任意の平面的グラフ G の閉路マトロイド M(G) は、当然双対を持つが、これは G の双対平面グラフ G* のマトロイドと(平面埋め込みの方法によらず)同一である。

組合せ理論

組合せ最適化問題は独立性システム [math](E,F)[/math] とコスト関数 [math]c : F \to \mathbb{R}[/math] を与えられたとき [math]\sum_{e \in X}c(e)[/math] を最大にする [math]X \in F[/math] を求める最大化問題か、最小にする基を求める最小化問題に定式化できる。なお、コスト関数の符号を反転することによって、最小化問題から最大化問題あるいはその逆にできる。

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

貪欲法

2つの貪欲法を示し、マトロイドにおいてはこの2つに対しては最適解が得られることを示す。なお、この2つは貪欲法の全てを網羅しているわけではなく、クラスカル法はここの枠組みで説明できるが、プリム法ダイクストラ法は、ここの枠組みでは扱えない。

最良選択貪欲法

独立性システム [math](E,F)[/math] とコスト関数 [math]c : E \to \mathbb{R}_{+}[/math] に対する最大化問題を解く。最良選択貪欲法は、[math]c(e)[/math] が最大である [math]e \in E[/math] から答えとなる集合 [math]E_{ans}[/math] に入れる。つまり、

  1. [math]c(e_1) \ge c(e_2) \ge \cdots \ge c(e_n)[/math] となるように [math]E = \{e_1, e_2, \cdots, e_n\}[/math]ソートする。
  2. [math]E_{ans} \leftarrow \emptyset[/math] 。次のステップで解に含まれる [math]e \in E[/math] を入れていき、最終的に解を [math]E_{ans}[/math] とする。
  3. For i = 1 to n : [math]E_{ans} \cup \{ e_i \} \in F[/math] ならば [math]E_{ans} \leftarrow E_{ans} \cup \{ e_i \}[/math]

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

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

[math]q(E,F) \le \frac{G}{OPT} \le 1[/math]

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

最悪棄却貪欲法

次に独立性システム (E,F) とコスト関数 [math]c:E\to\mathbb{R}_{+}[/math]に対する最小化問題を解こう。最悪棄却貪欲法は、都合の悪い e∈E から解から除外する。つまり、

  1. c(e1)≧c(e2)≧…≧c(en)となるようにE={e1,e2,…,en}をソートする。
  2. f=Eとする。次のステップでfからコストの高い順にeを除去する。
  3. For i=1 to n : [math]f\setminus\{e_i\}[/math]が基を含むならば新たなfを[math]f\setminus\{e_i\}[/math]とする。

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

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

[math]1\le\frac{G}{OPT}\le\max_{X\subseteq{E}}\frac{|X|-\rho^*(X)}{|X|-r^*(X)}[/math]

と書ける[7]。マトロイドならばρ*=r*なので、常に最適解を得られることが分かる。

オラクル

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

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

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

近似

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

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

[math]\frac{1}{1+\epsilon}c(S){\le}c(S'){\le}(1+\epsilon)c(S)[/math]

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

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

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

マトロイドの交差・分割

今までは具体的な問題を独立性システムやマトロイドに一般化して様々な定理を得てきたが、ここでは独立性システム間に関する様々な考察を取り上げる。

交差

2つの独立性システム(E,F),(E,F')とするとき、(E,F∩F')を2つの独立性システムの交差(intersection)と呼ぶ。任意の独立性システム(E,F)はp個のマトロイドの交差で表せ、ランク商q(E,F)≧1/pであるので、最良選択貪欲法での解を見積もることができる。専ら興味が持たれるのは2つのマトロイドの交差である。例えば2部グラフマッチング問題を考えよう。Eを辺集合、Fをマッチング集合とすれば、2部グラフだから点集合はA∪Bと書ける。F1を任意の点a∈Aに繋がる辺は高々1本であるという条件とするならば(E,F1)はマトロイドであり、同様にF2を任意の点b∈Bに繋がる辺は高々1本であるという条件とするならば(E,F2)もマトロイドである。F=F1∩F2なので、(E,F)は2つのマトロイド(E,F1),(E,F2)の交差である。

  • マトロイド交差問題(Matroid Intersection Problem) - 2つのマトロイド(E,F1),(E,F2)が与えられたとき、|F|が最大となるようなF∈F1∩F2を求めよ。

2つのマトロイド(E,F1),(E,F2)のランク関数をそれぞれr1,r2とすると、

[math]max\{|X|:X{\in}F_1{\cap}F_2\}=min\{r_1(W)+r_2(E\setminus{W}):W\subseteq{E}\}[/math]

となる[15]。マトロイド交差問題は多項式時間で解けるが、3つのマトロイドを考えるとそれはNP困難問題である。

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

分割

k個のマトロイド(E,F1),...,(E,Fk)についてX⊆EはX=X1∪…∪XkとなるようなXi∈Fi(i=1,...,k)が存在するとき、分割可能(partitionable)と呼ぶ。また、Fが分割可能ならば(E,F)は(E,F1),...,(E,Fk)の合併(union)あるいは(sum)と呼ばれる。

マトロイドの交差は、必ずしもマトロイドにはならなかったが、マトロイドの合併はマトロイドになる。k個のマトロイド(E,F1),...,(E,Fk)の各ランク関数をr1,...,rkとすると、これらの合併(E,F)のランク関数は

[math]r(X)=\min_{A{\subseteq}X}(|X\setminus{A}|+\sum_{i=1}^kr_i(A))[/math]

である[17]

次の問題とマトロイド交差問題は等価である。

  • マトロイド分割問題(Matroid Partitioning Problem) - k個のマトロイド(E,F1),...,(E,Fk)が与えられたとき|X|が最大になるような分割可能なX⊆Eを答えよ。

一般化

(詳細は各項目を参照のこと)

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

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

脚注

注釈

  1. 記号の意味については「冪集合」「空集合」「集合間の関係を表す記号」「濃度 (数学)」「和集合」「差集合」を参照のこと
  2. (R3),(R5),(R6)を満たす関数と(R1),(R2),(R4)を満たす関数は同値
  3. Xの基でないことに注意
  4. 概念は「多項式時間変換」に詳しい
  5. 最良選択貪欲法を使うことによって(本質的には独立性オラクルを複数回使うことによって)基決定オラクルを作れるが、逆に基決定オラクルを多項式回使っても独立性オラクルを作れない

出典

  1. D. Hausmann; B. Korte , T. A. Jenkyns (1980). “Worst case analysis of greedy type algorithms for independence systems”. Mathematical Programming Studies 12: pp.120-131. 
  2. Hassler Whitney (7 1935). “On the abstract properties of linear dependence” (pdf). American Journal of Mathematics 57: pp.509-533. http://www.math.osu.edu/~chmutov/wor-gr-su06/ref/Wh.pdf . 2011閲覧.. 
  3. T.A. Jenkyns (1976). “The Efficacy of the greedy Algorithm”. Proc. of 7th S-E. Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg: pp.341-350. 
  4. Bernhard Korte; Dirk Hausmann (1978). “An Analysis of the greedy heuristic for independence systems”, in B. Alspach, P. Hell, D.J. Miller, eds.: Aogorithmic Aspects of Combinatorics; Annals of Discrete Mathematics. Amsterdam: North-Holland, pp.65-74. 
  5. R. Rado (1957). “Note on Independence Functions”. Proceedings of the London Mathematical Society 7: pp.300-320. 
  6. Jack Edmonds (1971). “Matroids and the greedy algorithm”. Mathematical Programming 1: pp.127-136. 
  7. Bernhard Korte; C.L. Monma (1979). “Some remarks on a classification of oracle-type algorithms”, in L. Collatz, G. Meinardus, W. Wetterling, eds.: Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen. Basel: Birkhäuser, pp. 195-215. 
  8. Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”, in R. E. Miller and J. W. Thatcher eds: Complexity of Computer Computations. New York: Plenum, pp. 85-103. 
  9. D. Hausmann; B. Korte (1981). “Algorithmic versus axiomatic definitions of matroids”. Mathematical Programming Study 14: pp.98-111. 
  10. B. Korte; R. Schrader (1981). “On the existence of fast approximation schemes”, in O. Mangaserian, R.R. Meyer, S.M. Robinson, eds.: Nonlinear Programming. New York: Academic Press, pp. 415-437. 
  11. Oscar H. Ibarra; Chul E. Kim (10 1975). “Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems”. Journal of the ACM 22 (4): pp. 463-468. doi:10.1145/321906.321909. ISSN 0004-5411. 
  12. Sartaj K. Sahni (1 1976). “Algorithms for Scheduling Independent Tasks”. Journal of the ACM 23 (1): pp. 116-127. doi:10.1145/321921.321934. ISSN 0004-5411. 
  13. G.V. Gens (1979). “Computational complexity of approximation algorithms for combinatorial problems”, in J. Becvar, ed.: Mathematical Foundations of Computer Science. Berlin: Springer, pp. 292-300. 
  14. Eugene L. Lawler (1979). “Fast Approximation Algorithms for Knapsack Problems”. Mathematics of Operations Research 4: pp. 339-356. doi:10.1287/moor.4.4.339. 
  15. J. Edmonds (1970). “Submodular functions, matroids and certain polyhedra”, in R. Guy, H. Hanani, N. Sauer, J. Schonheim, eds.: Combinatorial Structures and Their Applications. New York: Gordon and Breach, pp.69-87. 
  16. A. Frank (1981). “A weighted matroid intersection algorithm”. Journal of Algorithms 2: pp.328-336. 
  17. Crispin Nash-Williams (1967). “An application of matroids to graph theory”, in P.Rosenstiehl, ed.: Theory of Graphs; proceedings of an international symposium in Rome 1966. New York: Gordon and Breach, pp.263-265. 
  18. M. Grötschel; L. Lovász, A. Schrijver (1981). “The ellipsoid method and its consequences in combinatorial optimization” (pdf). Combinatorica 1: pp.169-197. http://oai.cwi.nl/oai/asset/10046/10046A.pdf . 2011閲覧.. 
  19. Alexander Schrijver (2000). “A combinatorial algorithm minimizing submodular functions in strongly polynomial time” (pdf). Journal of Combinatorial Theory, Series B 80 (2): 346-355. http://homepages.cwi.nl/~lex/files/minsubm6.pdf . 2011閲覧.. 

参考文献

  1. B.コルテ・J.フィーゲン 『組合せ最適化-理論とアルゴリズム』 浅野孝夫,平田富夫,小野孝男,浅野泰仁訳、シュプリンガー・ジャパン、2012-2-29、第2版。ISBN 978-4621062029。

関連項目

分野

数学的対象