マトロイド交差点

組み合わせ最適化において、マトロイド交差問題とは、同一の基底集合上の2つのマトロイドにおいて、最大の共通独立集合を見つける問題である。マトロイドの要素に実数重みが割り当てられている場合、重み付きマトロイド交差問題とは、可能な限り最大の重みを持つ共通独立集合を見つける問題である。これらの問題は、二部グラフにおける最大マッチングや最大重みマッチングの探索、有向グラフにおける有向枝の探索など、グラフ理論や組み合わせ最適化における多くの問題を一般化したものである。

ジャック・エドモンズによるマトロイド交差定理[1]は、任意の²^つ^のマトロイドに対して、 $M_{1}=(E,{\mathcal {I}}_{1})$ そして $M_{2}=(E,{\mathcal {I}}_{2})$ 我々は持っています

\max _{I\in {\mathcal {I}}_{1}\cap {\mathcal {I}}_{2}}|I|=\min _{A\subseteq E}(r_{1}(A)+r_{2}(E\setminus A))

どこ $r_{1}$ そして $r_{2}$ は、それぞれのランク関数である。 $M_{1}$ そして $M_{2}$ 言い換えれば、常に単純な上限証明が存在し、それは2つのマトロイド間で基底集合を分割し、その値（それぞれのランクの合計）が最大共通独立集合のサイズに等しくなるというものである。

この定理に基づき、2つのマトロイドの交差問題は、マトロイド分割アルゴリズムを用いることで多項式時間で解くことができる。

例

G = ( U , V ; E ) を二部グラフとする。基底集合E上に分割マトロイドM _Uを定義することができる。このマトロイドでは、 U内のどの 2 つの端点も同じでない場合に、辺の集合は独立である。同様に、 V内のどの 2 つの端点も同じでない場合に、辺の集合は独立であるマトロイドM _Vを定義することができる。M UとM _Vの両方で独立である辺の集合は、どの 2 つの辺も端点を共有しないという性質を持つ。つまり、マッチングである。したがって、 M _UとM _Vの最大の共通独立集合は、_Gにおける最大マッチングである。

_{同様に、各エッジに}重みがある場合、 MUとM _Vの最大重み独立集合はGにおける最大重みマッチングになります。

アルゴリズム

重み付きマトロイド交差には、実行時間が異なる多項式時間アルゴリズムがいくつか存在する。実行時間は、 $n$ - 共通基本セットの要素数、 $r$ - 2 つのマトロイドのランク間の最大値、 $T$ -回路探索オラクルに必要な操作の数、および $k$ - 交差部分の要素数（特定のサイズの交差部分を見つけたい場合） $k$ )

エドモンズのアルゴリズムは線形計画法と多面体を使用する。^{[ 1 ]}
ローラーのアルゴリズム。^{[ 2 ]}
伊里と富沢のアルゴリズム^{[ 3 ]}
アンドラス・フランクのアルゴリズム^{[ 4 ]}は $O(n^{3}T)$ 算術演算。
Orlinと Vande-Vate のアルゴリズム。^{[ 5 ]}
カニンガムのアルゴリズム^{[ 6 ]}は、 $O(r^{1.5}nT)$ 一般マトロイドに対する演算、および $O(nr^{2}\log {r})$ 2つのr × n行列に対する線形マトロイドの操作。
Brezovec、Cornuejos、Glover ^{[ 7 ]}は、重み付きマトロイド交差のための 2 つのアルゴリズムを提示しています。
- 最初のアルゴリズムでは、すべての重みが整数である必要があり、カーディナリティの交差を見つけます。 $k$ 時間が経つにつれて $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ 。
- 2番目のアルゴリズムは時間内に実行されます $O(nr\cdot (\log {n}+r+T))$ 。
Huang、Kakimura、Kamiyama ^{[ 8 ]}は、重み付きマトロイド交差問題は、重みなしマトロイド交差問題のW個のインスタンスを解くことで解決できることを示している。ここでWは最大の与えられた重みであり、すべての与えられた重みは整数であると仮定する。このアルゴリズムは、 Wが小さい場合、以前のアルゴリズムよりも高速である。彼らはまた、e近似解を見つける近似アルゴリズムも提示している。 $O(\epsilon ^{-1}\log {r})$ 重み付けされていないマトロイド交差問題の例。ここで、rは 2 つの入力マトロイドの小さい方のランクである。
Ghosh、Gurjar、Raj ^{[ 9 ]}は並列計算モデルにおけるマトロイド交差の実行時間複雑性を研究している。
Bérczi、Király、Yamaguchi、Yokoi ^{[ 10 ]}は、より制限されたオラクルを使用して重み付きマトロイド交差のための強力な多項式時間アルゴリズムを発表しています。

拡張機能

カーディナリティを考慮した重みの最大化

重み付きマトロイド交差の変種である「(P _{k )」では、}k の濃度を持つすべての集合の中から、可能な限り最大の重みを持つ共通の独立集合を見つけることが目標です（そのような集合が存在する場合）。この変種も多項式時間で解くことができます。^{[ 7 ]}

3つのマトロイド

マトロイド交差問題は、2つのマトロイドだけでなく、3つのマトロイドが関係する場合、NP困難となる。

この困難性の証明の一つは、有向グラフにおけるハミルトン経路問題からの還元を利用しています。n 個の頂点を持つ有向グラフGと、指定されたノードsおよびtが与えられたとき、ハミルトン経路問題は、 sから始まりtで終わる長さn − 1の単純経路が存在するかどうかを判定する問題です。一般性を失うことなく、 s には入力エッジがなく、tには出力エッジがないと仮定できます。すると、ハミルトン経路が存在するのは、グラフのエッジ集合上の 3 つのマトロイドの交差部分にn − 1 個の要素の集合が存在する場合のみです。これらの 3 つのマトロイドは、選択されたエッジ集合の入次数と出次数が両方とも最大で 1 であることを保証する 2 つの分割マトロイドと、Gのエッジの向きを忘れることによって形成される無向グラフのグラフィックマトロイドであり、選択されたエッジ集合にサイクルがないことを保証します。^[¹¹^]

マトロイドパリティ

マトロイドに関する別の計算問題であるマトロイドパリティ問題は、Lawler ^{[ 12 ]}によってマトロイド交差と非二部グラフマッチングの一般的な一般化として定式化されました。しかし、線形マトロイドの場合は多項式時間で解くことができますが、他のマトロイドの場合はNP困難であり、マトロイドオラクルモデルでは指数時間が必要です。^{[ 13 ]}

評価済みマトロイド

評価付きマトロイドとは、基底の集合上に値関数vを備えたマトロイドであり、次の交換特性を持つ。任意の 2 つの異なる基底に対して、 $A$ そして $B$ 、もし $a\in A\setminus B$ ならば、要素が存在する $b\in B\setminus A$ 両方とも $(A\setminus \{a\})\cup \{b\}$ そして $(B\setminus \{b\})\cup \{a\}$ は基底であり、: $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ 。

重み付き二部グラフG = ( X + Y , E ) と、基底集合B _Xと評価値v _Xを持つX上のマトロイドと、基底B _Yと評価値v _Yを持つY上のマトロイドの 2 つが与えられたとき、評価付き独立割り当て問題は、 G内のマッチングMを見つける問題であり、M _X ( MによってマッチングされるXの部分集合) はB _Xの基底であり、M _YはB _Yの基底であり、この条件の下で、合計が $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ を最大化します。重み付きマトロイド交差問題は、マトロイド評価が一定である特殊なケースなので、最大化することだけを求めます。 $w(M)$ 制約条件は、M _XはB _Xの基底であり、M _YはB _Y の基底である。^{[ 14 ]}室田はこの問題に対する多項式時間アルゴリズムを提示している。^{[ 15 ]}

参考文献

1 2エドモンズ、ジャック (1970)、「劣モジュラ関数、マトロイド、および特定の多面体」、R. ガイ、H. ハナム、N. ザウアー、J. ショーンハイム (編)、『組合せ構造とその応用 (1969 年カルガリー会議議事録)』、ゴードン・アンド・ブリーチ、ニューヨーク、69-87ページ。 M. Jünger et al. に転載。 (編): Combinatorial Optimization (Edmonds Festschrift)、LNCS 2570、1126 ページ、Springer-Verlag、2003 年。
↑ Lawler, Eugene L. (1975), "Matroid intersection algorithms", Mathematical Programming , 9 (1): 31–56 , doi : 10.1007/BF01681329 , S2CID 206801650
↑イリ、マサオ。富沢伸明（1976）。「最適な「独立課題」を見つけるアルゴリズム」" .日本オペレーションズ・リサーチ学会論文誌. 19 (1): 32–57 . doi : 10.15807/jorsj.19.32 .
↑ Frank, András (1981)、「重み付きマトロイド交差アルゴリズム」、Journal of Algorithms、2 (4): 328–336、doi : 10.1016/0196-6774(81)90032-8
↑ Orlin, James B.; VandeVate, John (1983). On a "primal" matroid intersection algorithm (Sloan School of Management Working Paper #1446-83). hdl : 1721.1/2050 .
↑ Cunningham, William H. (1986-11-01). "Improved Bounds for Matroid Partition and Intersection Algorithms" . SIAM Journal on Computing . 15 (4): 948–957 . doi : 10.1137/0215066 . ISSN 0097-5397 .
1 2 Brezovec, Carl; Cornuéjols, Gérard ; Glover, Fred (1986)、「重み付きマトロイド交差のための2つのアルゴリズム」、Mathematical Programming、36 (1): 39–53、doi : 10.1007/BF02591988、S2CID 34567631
↑ Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki (2019-09-01). "重み付きマトロイド交差の厳密アルゴリズムと近似アルゴリズム" . Mathematical Programming . 177 (1): 85– 112. doi : 10.1007/s10107-018-1260-x . hdl : 2324/1474903 . ISSN 1436-4646 . S2CID 254138118 .
↑ Ghosh, Sumanta; Gurjar, Rohit; Raj, Roshan (2022-01-01), "重み付きマトロイド交差探索から決定への決定論的並列削減" , Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , Proceedings, Society for Industrial and Applied Mathematics, pp. 1013– 1035, doi : 10.1137/1.9781611977073.44 , ISBN 978-1-61197-707-3S2CID 245799113、2022年11月28日取得
↑ベルツィ、クリストフ;キラーリ、タマス。山口祐太郎；横井優 (2022-09-28)。「制限されたオラクルの下でのマトロイド交差点」。arXiv : 2209.14516 [ cs.DS ]。
↑ウェールズ語、DJA (2010) [1976]、マトロイド理論、Courier Dover Publications、p. 131、ISBN 9780486474397。
↑ Lawler, Eugene L. (1976), "第9章：マトロイドのパリティ問題" , 『組合せ最適化：ネットワークとマトロイド』、ニューヨーク：Holt, Rinehart and Winston、pp. 356–367、MR 0439106 。
↑ Jensen, Per M.; Korte, Bernhard (1982), "マトロイド特性アルゴリズムの複雑性", SIAM Journal on Computing , 11 (1): 184–190 , doi : 10.1137/0211014 , MR 0646772 。
↑室田和夫 (1996-11-01). "値付きマトロイド交差 I: 最適性基準" . SIAM Journal on Discrete Mathematics . 9 (4): 545– 561. doi : 10.1137/S0895480195279994 . ISSN 0895-4801 .
↑室田和夫 (1996 年 11 月)。「評価されたマトロイド交差 II: アルゴリズム」。離散数学に関する SIAM ジャーナル。9 (4): 562–576。土井: 10.1137/S0895480195280009。ISSN 0895-4801。

さらに読む

アイグナー、マーティン、ダウリング、トーマス（1971）「組合せ幾何学のマッチング理論」、アメリカ数学会紀要、158（1）：231–245、doi：10.1090/S0002-9947-1971-0286689-5。
Frederickson, Greg N.; Srinivas, Mandayam A. (1989)、「拡張されたマトロイド交差問題のためのアルゴリズムとデータ構造」（PDF）、SIAM Journal on Computing、18（1）：112–138、doi：10.1137/0218008、hdl：1802/6137、2017年9月22日にオリジナルからアーカイブ済み。
Gabow, Harold N. ; Tarjan, Robert E. (1984)、「マトロイド交差問題群に対する効率的なアルゴリズム」、Journal of Algorithms、5 (1): 80–131、doi : 10.1016/0196-6774(84)90042-7…

[:0-1] 1 2エドモンズ、ジャック (1970)、「劣モジュラ関数、マトロイド、および特定の多面体」、R. ガイ、H. ハナム、N. ザウアー、J. ショーンハイム (編)、『組合せ構造とその応用 (1969 年カルガリー会議議事録)』、ゴードン・アンド・ブリーチ、ニューヨーク、69-87ページ。 M. Jünger et al. に転載。 (編): Combinatorial Optimization (Edmonds Festschrift)、LNCS 2570、1126 ページ、Springer-Verlag、2003 年。

[2] Lawler, Eugene L. (1975), "Matroid intersection algorithms", Mathematical Programming , 9 (1): 31–56 , doi : 10.1007/BF01681329 , S2CID 206801650

[3] イリ、マサオ。富沢伸明（1976）。「最適な「独立課題」を見つけるアルゴリズム」" .日本オペレーションズ・リサーチ学会論文誌. 19 (1): 32–57 . doi : 10.15807/jorsj.19.32 .

[4] Frank, András (1981)、「重み付きマトロイド交差アルゴリズム」、Journal of Algorithms、2 (4): 328–336、doi : 10.1016/0196-6774(81)90032-8

[5] Orlin, James B.; VandeVate, John (1983). On a "primal" matroid intersection algorithm (Sloan School of Management Working Paper #1446-83). hdl : 1721.1/2050 .

[6] Cunningham, William H. (1986-11-01). "Improved Bounds for Matroid Partition and Intersection Algorithms" . SIAM Journal on Computing . 15 (4): 948–957 . doi : 10.1137/0215066 . ISSN 0097-5397 .

[:1-7] 1 2 Brezovec, Carl; Cornuéjols, Gérard ; Glover, Fred (1986)、「重み付きマトロイド交差のための2つのアルゴリズム」、Mathematical Programming、36 (1): 39–53、doi : 10.1007/BF02591988、S2CID 34567631

[8] Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki (2019-09-01). "重み付きマトロイド交差の厳密アルゴリズムと近似アルゴリズム" . Mathematical Programming . 177 (1): 85– 112. doi : 10.1007/s10107-018-1260-x . hdl : 2324/1474903 . ISSN 1436-4646 . S2CID 254138118 .

[9] Ghosh, Sumanta; Gurjar, Rohit; Raj, Roshan (2022-01-01), "重み付きマトロイド交差探索から決定への決定論的並列削減" , Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , Proceedings, Society for Industrial and Applied Mathematics, pp. 1013– 1035, doi : 10.1137/1.9781611977073.44 , ISBN 978-1-61197-707-3S2CID 245799113、2022年11月28日取得

[10] ベルツィ、クリストフ;キラーリ、タマス。山口祐太郎；横井優 (2022-09-28)。「制限されたオラクルの下でのマトロイド交差点」。arXiv : 2209.14516 [ cs.DS ]。

[11] ウェールズ語、DJA (2010) [1976]、マトロイド理論、Courier Dover Publications、p. 131、ISBN 9780486474397。

[12] Lawler, Eugene L. (1976), "第9章：マトロイドのパリティ問題" , 『組合せ最適化：ネットワークとマトロイド』、ニューヨーク：Holt, Rinehart and Winston、pp. 356–367、MR 0439106 。

[13] Jensen, Per M.; Korte, Bernhard (1982), "マトロイド特性アルゴリズムの複雑性", SIAM Journal on Computing , 11 (1): 184–190 , doi : 10.1137/0211014 , MR 0646772 。

[14] 室田和夫 (1996-11-01). "値付きマトロイド交差 I: 最適性基準" . SIAM Journal on Discrete Mathematics . 9 (4): 545– 561. doi : 10.1137/S0895480195279994 . ISSN 0895-4801 .

[15] 室田和夫 (1996 年 11 月)。「評価されたマトロイド交差 II: アルゴリズム」。離散数学に関する SIAM ジャーナル。9 (4): 562–576。土井: 10.1137/S0895480195280009。ISSN 0895-4801。

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

例