https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96
劣モジュラ最適化 - 版の履歴
2026-04-13T18:20:01Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96&diff=9946&oldid=prev
2008年8月6日 (水) 04:01にImahoriによる
2008-08-06T04:01:33Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年8月6日 (水) 04:01時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l43" >43行目:</td>
<td colspan="2" class="diff-lineno">43行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>で定義される量を交換容量と呼ぶ. </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>で定義される量を交換容量と呼ぶ. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> 基多面体上では, 貪欲アルゴリズムによって, 線型目的関数の最適化が可能である. 一般に, 楕円体法を通じて, 最適化問題と分離問題とが計算量の多項式性という観点からは等価であるという原理に基づいて, 強多項式時間で劣モジュラ関数の最小化が可能であることが示されている [3] . しかし, 楕円体法は実際上効率的とは言い難く, <del class="diffchange diffchange-inline">組合せ的な多項式時間アルゴリズムの開発が望まれている</del>. <del class="diffchange diffchange-inline">(最近</del>, Iwata-Fleischer-Fujishige[6]とSchrijver[7]によって独立に解決された. <del class="diffchange diffchange-inline">) </del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> 基多面体上では, 貪欲アルゴリズムによって, 線型目的関数の最適化が可能である. 一般に, 楕円体法を通じて, 最適化問題と分離問題とが計算量の多項式性という観点からは等価であるという原理に基づいて, 強多項式時間で劣モジュラ関数の最小化が可能であることが示されている [3] . しかし, 楕円体法は実際上効率的とは言い難く, <ins class="diffchange diffchange-inline">組合せ的な多項式時間アルゴリズムの開発が望まれていた</ins>. </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">2000年前後に</ins>, Iwata-Fleischer-Fujishige[6]とSchrijver[7]によって独立に解決された. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 有向グラフ <math>G=(N,A)\, </math> と, <math>f(N)=0\, </math> を満たす <math>N\, </math> 上の劣モジュラシステム <math>(\mathcal {D},f)\, </math> を考える. 各枝 <math>a\, </math> の始点を <math>\partial^+a\, </math>, 終点を <math>\partial^-a\, </math> と書き, <math>X\subseteq N\, </math> から出る枝の集合を <math>\Delta^+X\, </math>, 入る枝の集合を <math>\Delta^-X\, </math> と表す. 任意の <math>\varphi\in\mathbf {R}^A\, </math> に対して, 境界 <math>\partial\varphi\in\mathbf {R}^N\, </math> を <math>\partial\varphi(X)=\varphi(\Delta^+X)-\varphi(\Delta^-X)\, </math> で定める. [[劣モジュラフロー問題]] (submodular flow problem) とは, 枝流量の上下限 <math>\bar {c},\underline {c}\in\mathbf {R}^A\, </math> と費用 <math>d\in\mathbf {R}^A\, </math> が与えられたとき, </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 有向グラフ <math>G=(N,A)\, </math> と, <math>f(N)=0\, </math> を満たす <math>N\, </math> 上の劣モジュラシステム <math>(\mathcal {D},f)\, </math> を考える. 各枝 <math>a\, </math> の始点を <math>\partial^+a\, </math>, 終点を <math>\partial^-a\, </math> と書き, <math>X\subseteq N\, </math> から出る枝の集合を <math>\Delta^+X\, </math>, 入る枝の集合を <math>\Delta^-X\, </math> と表す. 任意の <math>\varphi\in\mathbf {R}^A\, </math> に対して, 境界 <math>\partial\varphi\in\mathbf {R}^N\, </math> を <math>\partial\varphi(X)=\varphi(\Delta^+X)-\varphi(\Delta^-X)\, </math> で定める. [[劣モジュラフロー問題]] (submodular flow problem) とは, 枝流量の上下限 <math>\bar {c},\underline {c}\in\mathbf {R}^A\, </math> と費用 <math>d\in\mathbf {R}^A\, </math> が与えられたとき, </div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l77" >77行目:</td>
<td colspan="2" class="diff-lineno">78行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''参考文献'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''参考文献'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[1] J. Edmonds and R. Giles, "A min-max relation for submodular functions on graphs," in ''Studies in Integer Programming''<del class="diffchange diffchange-inline">}</del>, P. L. Hammer, E. L. Johnson, and B. H. Korte, eds., North-Holland, 185-204, 1977. </div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[1] J. Edmonds and R. Giles, "A min-max relation for submodular functions on graphs," in ''Studies in Integer Programming'', P. L. Hammer, E. L. Johnson, and B. H. Korte, eds., North-Holland, 185-204, 1977. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[2] S. Fujishige, ''Submodular Functions and Optimization'', 2nd ed., Elsevier, 2005.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[2] S. Fujishige, ''Submodular Functions and Optimization'', 2nd ed., Elsevier, 2005.</div></td></tr>
</table>
Imahori
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96&diff=9690&oldid=prev
Imahori: 基礎編と用語編のマージ
2008-03-13T14:11:25Z
<p>基礎編と用語編のマージ</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年3月13日 (木) 14:11時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【れつもじゅらさいてきか (submodular optimization)】'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【れつもじゅらさいてきか (submodular optimization)】'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 概要 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ関数に関連した最適化問題に 対しては, 離散構造を利用した効率的なアルゴリズムが存在することが少なくない. そのため, 劣モジュラ最適化は, 非線形最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ関数に関連した最適化問題に 対しては, 離散構造を利用した効率的なアルゴリズムが存在することが少なくない. そのため, 劣モジュラ最適化は, 非線形最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">詳しくは</del>[[<del class="diffchange diffchange-inline">《劣モジュラ最適化》</del>|<del class="diffchange diffchange-inline">基礎編：劣モジュラ最適化</del>]]<del class="diffchange diffchange-inline">を参照</del>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=== 詳説 ===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>[[<ins class="diffchange diffchange-inline">劣モジュラ最適化]] (submodular optimization) とは, [[劣モジュラ関数]] (submodular function) を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ最適化は, 非線型最適化における凸最適化のように, 離散最適化における基本的な位置を占めている. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 有限集合 <math>N\, </math> の部分集合族 <math>\mathcal {D}\subseteq 2^N\, </math> が, <math>\emptyset\, </math> と <math>N\, </math> を共に含み, 任意の <math>X,Y\in\mathcal {D}\, </math> に対して <math>X\cup Y, X\cap Y\in\mathcal {D}\, </math> を満たすものとする. このとき, <math>\mathcal {D}\, </math> は分配束をなす. 関数 <math>f:\mathcal {D}\to\mathbf {R}\, </math> が, 任意の <math>X,Y\in\mathcal {D}\, </math> に対して </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)\, </math> </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">を満たすとき, <math>f\, </math> は劣モジュラ関数と呼ばれる. 不等号が常に等号で成立する場合には, <math>f\, </math> をモジュラ関数という. 分配束 <math>\mathcal {D}\, </math> と劣モジュラ関数 <math>f\, </math> の組 <math>(\mathcal {D},f)\, </math> は, <math>f(\emptyset)=0\, </math> のとき, [[劣モジュラシステム]] (submodular system) と呼ばれる. さらに, <math>\mathcal {D}=2^N\, </math> であり, <math>f\, </math> が単調性を有するとき, すなわち任意の <math>X,Y\subseteq N\, </math> に対して <math>X\subseteq Y \Rightarrow f(X)\leq f(Y)\, </math> が成り立つとき, <math>(N,f)\, </math> を[[ポリマトロイド]] (polymatroid)という. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> オペレーションズ・リサーチにおいて重要な劣モジュラ関数の代表的な例を以下に挙げる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''カット容量関数''' 有向グラフ <math>G=(N,A)\, </math> において, 各枝 <math>a\in A\, </math> に非負の容量 <math>c(a)\, </math> が与えられているとき, <math>\textstyle \kappa(X)=\sum\{c(a)\mid a\in \Delta^+X\}\, </math> で定義される容量関数 <math>\kappa:2^N\to\mathbf {R}\, </math> は, 劣モジュラ関数となる. ここで, <math>\Delta^+X\, </math> は, <math>X\subseteq N\, </math> から出る枝の集合を表す. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''マトロイド階数関数''' マトロイド <math>\mathcal {M}=(N,\mathcal {I})\, </math> において, 階数関数 <math>\rho:2^N\to\mathbf {Z}\, </math> を <math>\rho(X)=\max\{|I</ins>|<ins class="diffchange diffchange-inline">\mid I\subseteq X,\,I\in \mathcal {I}\}\, </math> で定めると, <math>(N,\rho)\, </math> はポリマトロイドとなる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''エントロピー関数''' 有限アルファベットの離散確率変数の集合 <math>N\, </math> に関して, 空でない部分集合 <math>X\subseteq N\, </math> のエントロピーを <math>\eta(X)\, </math> と書き, <math>\eta(\emptyset)=0\, </math> と定めると, <math>(N,\eta)\, </math> はポリマトロイドとなる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 有限集合 <math>N\, </math> 上の実数値関数全体のなす線型空間を <math>\mathbf {R}^N\, </math> と表す. ベクトル <math>x\in\mathbf {R}^N\, </math> は, 部分集合 <math>X\subseteq N\, </math> に対して <math>\textstyle x(X)=\sum\{x(i)\mid i\in X\}\, </math> と定義することによって, <math>x(\emptyset)=0\, </math> であるようなモジュラ関数 <math>x\, </math> と同一視される.劣モジュラシステム <math>(\mathcal {D},f)\, </math> は, <math>\mathbf {R}^N\, </math> 中の[[基多面体]] (base polyhedron)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>\mbox{B}(f)=\{x\mid x\in\mathbf {R}^N,\;x(N)=f(N),\;\forall X\in\mathcal {D}: x(X)\leq f(X)\} \, </math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">を定める. 基 <math>x\in\mbox{B}(f)\, </math> と相異なる <math>i,j\in N\, </math> に対して, </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>\tilde{c}(x,i,j)=\min\{f(X)-x(X)\mid i\in X\in\mathcal {D}, j\notin X\}\, </math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">で定義される量を交換容量と呼ぶ. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 基多面体上では, 貪欲アルゴリズムによって, 線型目的関数の最適化が可能である. 一般に, 楕円体法を通じて, 最適化問題と分離問題とが計算量の多項式性という観点からは等価であるという原理に基づいて, 強多項式時間で劣モジュラ関数の最小化が可能であることが示されている [3] . しかし, 楕円体法は実際上効率的とは言い難く, 組合せ的な多項式時間アルゴリズムの開発が望まれている. (最近, Iwata-Fleischer-Fujishige[6]とSchrijver[7]によって独立に解決された. ) </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 有向グラフ <math>G=(N,A)\, </math> と, <math>f(N)=0\, </math> を満たす <math>N\, </math> 上の劣モジュラシステム <math>(\mathcal {D},f)\, </math> を考える. 各枝 <math>a\, </math> の始点を <math>\partial^+a\, </math>, 終点を <math>\partial^-a\, </math> と書き, <math>X\subseteq N\, </math> から出る枝の集合を <math>\Delta^+X\, </math>, 入る枝の集合を <math>\Delta^-X\, </math> と表す. 任意の <math>\varphi\in\mathbf {R}^A\, </math> に対して, 境界 <math>\partial\varphi\in\mathbf {R}^N\, </math> を <math>\partial\varphi(X)=\varphi(\Delta^+X)-\varphi(\Delta^-X)\, </math> で定める. [[劣モジュラフロー問題]] (submodular flow problem) とは, 枝流量の上下限 <math>\bar {c},\underline {c}\in\mathbf {R}^A\, </math> と費用 <math>d\in\mathbf {R}^A\, </math> が与えられたとき, </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>\min\{\sum_{a\in A}d(a)\varphi(a)\mid\partial\varphi\in\mbox{B}(f),\; </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\forall a\in A: \underline {c}(a)\leq\varphi(a)\leq\bar {c}(a)\}\, </math> </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">を求める問題である [1] . 特に, <math>f\, </math> がモジュラ関数の場合には, 最小費用フロー問題となることに注意する. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 劣モジュラフロー問題は, 任意の <math>X\in\mathcal {D}\, </math> に対して<math>\underline {c}(\Delta^+X)-\bar {c}(\Delta^-X)\leq f(X)\, </math> が成立するとき, かつそのときに限り, 実行可能解を有する. さらに, <math>\bar {c},\underline {c},f\, </math> が整数値関数であれば, 整数実行可能解が存在する. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 実行可能解 <math>\varphi\, </math> は, 以下の条件を満たす <math>p\in\mathbf {R}^N\, </math> が存在するとき, かつそのときに限り, 最適解である. ただし, 各枝 <math>a\in A\, </math> に対して<math>d_p(a)=d(a)+p(\partial^+a)-p(\partial^-a)\, </math> と定める. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">*任意の <math>a\in A\, </math> に対して, <math>d_p(a)>0\Rightarrow\varphi(a)=\underline {c}(a)\, \, </math>, および<math>d_p(a)<0 \Rightarrow \varphi(a)=\bar {c}(a)\, </math>. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">*任意の相異なる <math>i,j\in N\, </math> に対して, <math>p(j)<p(i)\Rightarrow \tilde{c}(\partial\varphi,i,j)=0\, </math>. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">さらに, <math>d\, </math> が整数値関数の場合には, <math>p\, </math> を整数値関数に限ることができる.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 最小費用フロー問題の解法を一般化することによって, 劣モジュラフロー問題を解くアルゴリズムが提案されている [5] . これらの組合せ的なアルゴリズムは, いずれも劣モジュラシステム <math>(\mathcal {D},f)\, </math> に関する交換容量を計算する手続きの存在を仮定している. 交換容量の計算は, 定義より明らかなように, 劣モジュラ関数の最小化になっており, 楕円体法を用いれば強多項式時間で可能なことが知られている. しかし, 劣モジュラフロー問題の応用に際しては, 問題の特殊性を活かした組合せ的な手続きが設計できる場合が少なくない. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 劣モジュラ関数 <math>f\, </math> の最小値を達成する <math>X\in\mathcal {D}\, </math> の全体は, <math>\mathcal {D}\, </math> の部分分配束をなす. バーコフ(G. Birkhoff)の表現定理より, この部分分配束は <math>N\, </math> の適当な部分集合への分割と各成分間の半順序関係によって表すことができる. この原理に基づいて劣モジュラ関数で記述された離散システムを分解する手法を総称して[[基本分割]] (principal partition) と呼ぶ. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''参考文献'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[1] J. Edmonds and R. Giles, "A min-max relation for submodular functions on graphs," in ''Studies in Integer Programming''}, P. L. Hammer, E. L. Johnson, and B. H. Korte, eds., North-Holland, 185-204, 1977. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[2] S. Fujishige, ''Submodular Functions and Optimization'', 2nd ed., Elsevier, 2005.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[3] M. Gr&ouml;tschel, L. Lov\'asz and A. Schrijver, ''Geometric Algorithms and Combinatorial Optimization'', Springer-Verlag, 1988. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[4] 伊理正夫, 藤重悟, 大山逹雄, 『グラフ・ネットワーク・マトロイド』, 産業図書, 1986. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[5] 岩田覚, 「劣モジュラ流問題」, 藤重悟 編 『離散構造とアルゴリズム Ⅵ』, 近代科学社, 第4章，127-170, 1999.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[6</ins>] <ins class="diffchange diffchange-inline">S.Iwata, L.Fleischer and S.Fujishige, ''A combinatorial strongly polynomial algorithm for minimizing submodular functions'', Journal of ACM 48 (2001) , 761--777.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[7</ins>] <ins class="diffchange diffchange-inline">A</ins>.<ins class="diffchange diffchange-inline">Schrijver, ''A combinatorial algorithm minimizing submodular functions in strongly polynomial time'', Journal of Combinatorial Theory, Ser. B, 80 (2000) , 346--355.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[[Category:グラフ･ネットワーク|れつもじゅらさいてきか]]</ins></div></td></tr>
</table>
Imahori
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96&diff=8337&oldid=prev
2007年8月8日 (水) 11:56にKanda.kによる
2007-08-08T11:56:25Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年8月8日 (水) 11:56時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ関数に関連した最適化問題に 対しては, 離散構造を利用した効率的なアルゴリズムが存在することが少なくない. そのため, 劣モジュラ最適化は, 非線形最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ関数に関連した最適化問題に 対しては, 離散構造を利用した効率的なアルゴリズムが存在することが少なくない. そのため, 劣モジュラ最適化は, 非線形最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">詳しくは[[《劣モジュラ最適化》|基礎編：劣モジュラ最適化]]を参照.</ins></div></td></tr>
</table>
Kanda.k
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96&diff=6525&oldid=prev
Orsjwiki: "劣モジュラ最適化" を保護しました。 [edit=sysop:move=sysop]
2007-07-20T00:57:56Z
<p>"劣モジュラ最適化" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月20日 (金) 00:57時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96&diff=2107&oldid=prev
122.17.2.240: 新しいページ: ''''【れつもじゅらさいてきか (submodular optimization)】''' 劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ...'
2007-07-09T07:48:14Z
<p>新しいページ: ''''【れつもじゅらさいてきか (submodular optimization)】''' 劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ...'</p>
<p><b>新規ページ</b></p><div>'''【れつもじゅらさいてきか (submodular optimization)】'''<br />
<br />
劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ関数に関連した最適化問題に 対しては, 離散構造を利用した効率的なアルゴリズムが存在することが少なくない. そのため, 劣モジュラ最適化は, 非線形最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.</div>
122.17.2.240