매트로이드 교차로

조합 최적화에서 매트로이드 교차 문제는 동일한 지면 집합에 걸쳐 두 매트로이드에서 가장 큰 공통 독립 집합을 찾는 것입니다.매트로이드의 요소에 실제 가중치가 할당된 경우 가중 매트로이드 교차 문제는 가능한 최대 가중치를 갖는 공통 독립 집합을 찾는 것입니다.이러한 문제는 이중 그래프에서 최대 일치 및 최대 가중치 일치를 찾는 것과 지시 그래프에서 수목원을 찾는 것을 포함하여 조합 최적화에서 많은 문제를 일반화합니다.

매트로이드 교점 정리는 ^[1]잭 에드먼즈에 의해 항상 두 매트로이드 사이에 지면 집합의 분할로 구성된 단순한 상한 인증서가 있으며, 이 인증서의 값(각 순위의 합)은 최대 공통 독립 집합의 크기와 같습니다.이 정리를 바탕으로, 두 개의 매트로이드에 대한 매트로이드 교차 문제는 매트로이드 분할 알고리즘을 사용하여 다항 시간 내에 해결할 수 있습니다.

예

G = (U,V,E)를 이분 그래프라고 합니다.하나는 U에서 동일한 엔드포인트를 갖는 에지들 중 어느 두 개도 없는 경우, 에지들의 집합이 독립적인 파티션 매트로이드_U M을 접지 집합 E에 정의할 수 있습니다. 마찬가지로, V에서 동일한 엔드포인트를 갖는 에지들 중 어느 두 개도 없는 경우, 에지들의 집합이 독립적인 매트로이드_V M을 정의할 수 있습니다.M과 M_V 모두에서_U 독립적인 가장자리 집합은 두 가장자리가 끝점을 공유하지 않는 속성을 갖습니다. 즉, 일치합니다.따라서 M과_V M의 가장_U 큰 공통 독립 집합은 G에서 최대 일치입니다.

마찬가지로 각 에지에 가중치가 있는 경우 M과_V M의 최대_U 가중치 독립 집합은 G의 최대 가중치 일치입니다.

알고리즘

가중 매트로이드 교차점에 대한 여러 다항식 시간 알고리즘이 있으며 실행 시간이 다릅니다.실행 시간은 n{\ $displaystyle$ n $}$ - 공통 베이스 세트의 요소 수, $r$ {\ $displaystyle$ r $}$ - 두 매트로이드의 순위 사이의 최대,T {\ $displaystyle$ T $}$ - 회로 찾기 오라클에 필요한 작업 수, $k$ ${\displaystyle$ k $}$ - 교차점에 있는 요소의 수(특정 $k$ 의k {\ $displaystyle$ k $}$ 의 교차점을 찾고자 하는 경우)

Edmonds의 알고리즘은 선형 프로그래밍과 ^[1]다면체를 사용합니다.
롤러의 알고리즘.^[2]
이리와 토미자와의 알고리즘^[3]
Andras Frank의 알고리즘은^[4] O $O(n^{3}T)$ {\ $displaystyle$ O $(n^{3}T)}$ 개의 $O(n^{3}T)$ 산술 연산을 $O(n^{3}T)$ 합니다.
올린과 반데베이트의 알고리즘.^[5]
Cunningham의 알고리즘을^[6] 사용하려면 일반 매트로이드에서 $O(r^{1.5}nT)$ $O(r^{1.5}nT)$ T) {\ $displaystyle O(r^{1.5}$ nT $O(r^{1.5}nT)$ )} 연산이 $O(r^{1.5}nT)$ 하고, $O(nr^{2}\log {r})$ 매트로이드에서 O $O(nr^{2}\log {r})$ $O(nr^{2}\log {r})$ log $O(nr^{2}\log {r})$ $O(nr^{2}\log {r})$ ${\displaystyle$ O $(nr^{2}\log {r})$ 연산이 $O(nr^{2}\log {r})$ 필요합니다.
Brezovec, Cornuejos 및 Glover는^[7] 가중 매트로이드 교차에 대한 두 가지 알고리듬을 제시합니다.
- 첫 번째 알고리즘은 모든 가중치가 정수여야 하며 시간 $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ 에서 $k$ k{\ $displaystyle$ k $}$ 의 교집합을 찾습니다 $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ 2 + $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ T ) ⋅ ( $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ ⁡ $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ ) $O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))$ {\ $displaystyle$ O $((n^{3}k^{2}$ + $nkT))\cdot (1+\log {W$
- 두 번째 알고리즘은 O $O(nr\cdot (\log {n}+r+T))$ 에 실행됩니다 $O(nr\cdot (\log {n}+r+T))$ r $O(nr\cdot (\log {n}+r+T))$ ⋅ ( $O(nr\cdot (\log {n}+r+T))$ ⁡ $O(nr\cdot (\log {n}+r+T))$ + $O(nr\cdot (\log {n}+r+T))$ r $O(nr\cdot (\log {n}+r+T))$ + T ) {\ $displaystyle O(nr\cdot$ (\log { $n}$ + $r$ + $T$
Huang, Kakimura 및 Kakiyama는^[8] 가중치 매트로이드 교차 문제가 가중치가 부여되지 않은 매트로이드 교차 문제의 W 인스턴스를 해결하면 가중치 매트로이드 교차 문제가 해결될 수 있음을 보여줍니다. 여기서 W는 주어진 가중치가 모두 적분이라고 가정할 때 가장 큰 가중치입니다.이 알고리즘은 W가 작을 때 이전 알고리즘보다 빠릅니다.그들은 또한 가중치 매트로이드 교차 문제의 O $O(\epsilon ^{-1}\log {r})$ (ϵ $O(\epsilon ^{-1}\log {r})$ - $O(\epsilon ^{-1}\log {r})$ log ⁡ $O(\epsilon ^{-1}\log {r})$ {\ $displaystyle$ O $(\epsilon ^{-1}\log {r})}$ 인스턴스를 $O(\epsilon ^{-1}\log {r})$ 하여 e-근사해를 찾는 근사 알고리듬을 제시합니다. 여기서 r은 두 입력 매트로이드 중 작은 순위입니다.
Ghosh, Gurjar 및^[9] Raj는 병렬 컴퓨팅 모델에서 매트로이드 교차점의 런타임 복잡성을 연구합니다.
Bérczi, Kiraly, Yamaguchi 및 Yokoi는^[10] 더 제한된 오라클을 사용하여 가중 매트로이드 교차점에 대한 강력한 다항식 시간 알고리듬을 제시합니다.

확장자

카디널리티에 따라 무게 극대화

"(P_k)"라고 불리는 가중 매트로이드 교집합의 변형에서, 목표는 그러한 집합이 존재할 경우 카디널리티 k를 갖는 모든 집합 중에서 가능한 최대 가중치를 갖는 공통 독립 집합을 찾는 것입니다.이 변형 역시 다항식 시간 ^[7]안에 해결할 수 있습니다.

삼매트로이드

매트로이드 교차 문제는 매트로이드가 2개만 포함된 것이 아니라 3개가 포함된 경우 NP-hard가 됩니다.

이 경도 결과에 대한 하나의 증거는 지시 그래프에서 해밀턴 경로 문제의 감소를 사용합니다.n개의 정점과 지정된 노드 및 t를 갖는 방향 그래프 G가 주어졌을 때, 해밀턴 경로 문제는 s에서 시작하여 t에서 끝나는 길이 n - 1의 단순 경로가 존재하는지 여부를 결정하는 문제입니다.s는 들어오는 에지가 없고 t는 나가는 에지가 없다고 일반성을 잃지 않고 가정할 수 있습니다.그런 다음 그래프의 가장자리 집합에서 세 개의 매트로이드의 교차점에 n - 1 요소의 집합이 있는 경우에만 해밀턴 경로가 존재합니다. 두 개의 분할 매트로이드는 선택한 가장자리 집합의 인-도 및 아웃-도가 모두 최대 하나임을 보장하고 가장자리 방향을 잊어버려 형성된 무방향 그래프의 그래픽 매트로이드입니다.선택한 에지 세트에 ^[11]사이클이 없음을 확인하는 G.

매트로이드 패리티

매트로이드에 대한 또 다른 계산 문제인 매트로이드 패리티 문제는 롤러에 의해^[12] 매트로이드 교차와 비이중입자 그래프 매칭의 일반적인 일반화로 공식화되었습니다.그러나 선형 매트로이드의 경우 다항 시간에 풀 수 있지만 다른 매트로이드의 경우 NP-hard이며 매트로이드 오라클 ^[13]모델에서는 지수 시간이 필요합니다.

평가 매트로이드

평가된 매트로이드는 다음과 같은 교환 속성을 가진 값 함수 v를 기본 집합에 장착한 매트로이드입니다. 임의의 두 개의 서로 다른 $A$ A{\ $displaystyle$ A} 및 $B$ {\ $displaystyle$ B $B$ 에 대해, $a\in A\setminus B$ A $a\in A\setminus B$ ∈ $a\in A\setminus B$ {\ $displaystyle$ a $\in$ A\ $setminus$ B $a\in A\setminus B$ 이면, 둘 $(A\setminus \{a\})\cup \{b\}$ 다 ( $(A\setminus \{a\})\cup \{b\}$ ∖ { $(A\setminus \{a\})\cup \{b\}$ })가 되는 $b\in B\setminus A$ b ∈ $b\in B\setminus A$ ${\displaystyle$ b $\in$ B $\setminus$ A $}$ 가 존재합니다. $(A\setminus \{a\})\cup \{b\}$ $(A\setminus \{a\})\cup \{b\}$ { $(A\setminus \{a\})\cup \{b\}$ $(A\setminus \{a\})\cup \{b\}$ ${\displaystyle ($ $(B\setminus \{b\})\cup \{a\}$ $\setminus$ \{ $a\})\cup$ \{ $(B\setminus \{b\})\cup \{a\}$ $(A\setminus \{a\})\cup \{b\}$ { $(B\setminus \{b\})\cup \{a\}$ {\ $displaystyle ($ B $\setminus$ \{ $b\})\$ cup \{ $a\}}$ 는 기본이고 : $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ ( $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ + $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ ( $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $(A\setminus \{a\})\cup \{b\}$ { $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ v $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ ( $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $(A\setminus \{a\})\cup \{b\}$ { $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ ) + $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ ( $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $(A\setminus \{a\})\cup \{b\}$ { $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $(A\setminus \{a\})\cup \{b\}$ { $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ ) $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$ {\ $displaystyle$ v ( $A)$ + $v (B\setminus$ \{ $b\}\cup$ \{ $a\})$ + $v$ ( $A\setminus$ \{ $a\}\cup$ \{ $b\})$ $v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})$

가중치가 부여된 이분 그래프 G = (X+Y, E) 및 두 개의 가치 매트로이드, 하나는 기저 집합 B 및 평가 v를 갖는 X 상, 하나는 기저 B 및 평가 v를 갖는 Y 상에서, 가치 독립 할당 문제는 M(M에 의해 매칭되는 X의 부분 집합)이 B의 기저이고, M은 B의 기저이며, 이에 종속되는,합 $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ w ( $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ ) + $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ X ( $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ ) + $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ ( $M$ ) {\ $displaystyle$ w ( M ) + $v_{X}$ ( $M_{X})$ + $v_{Y$ } ( $M_{Y})}$ 가 $w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})$ 최대가 됩니다.가중 매트로이드 교차 문제는 매트로이드 값이 일정한 특수한 경우이므로, M이_X B의_X 기저이고_Y M이 ^[14]B의_Y 기저인 w $w(M)$ ${\displaystyle$ w $(M)}$ 를 $w(M)$ $w(M)$ 하는 것만을 추구합니다. Murota는 이 ^[15]문제에 대한 다항 시간 알고리즘을 제시합니다.

참고 항목

Matroid partitioning - 관련 문제입니다.

참고문헌

^ ^a ^b Edmonds, Jack (1970), "Submodular functions, matroids, and certain polyhedra", in R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69–87M. Jünger et al. (Eds.): Edmonds, Jack (1970), "Submodular functions, matroids, and certain polyhedra", in R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69–87조합 최적화 (Edmonds Festschrift), LNCS 2570, pp. 1126, Springer-Verlag, 2003.
^ Lawler, Eugene L. (1975), "Matroid intersection algorithms", Mathematical Programming, 9 (1): 31–56, doi:10.1007/BF01681329, S2CID 206801650
^ Iri, Masao; Tomizawa, Nobuaki (1976). "An Algorithm for Finding an Optimal "Independent Assignment"". 日本オペレーションズ・リサーチ学会論文誌. 19 (1): 32–57. doi:10.15807/jorsj.19.32.
^ Frank, András (1981), "A weighted matroid intersection algorithm", Journal of Algorithms, 2 (4): 328–336, doi:10.1016/0196-6774(81)90032-8
^ Orlin, James B.; VandeVate, John; Management, Sloan School of (2012-06-07). "On a "primal" matroid intersection algorithm". {{cite journal}}:저널 요구사항 인용 journal=(도움말)
^ 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.
^ ^a ^b Brezovec, Carl; Cornuéjols, Gérard; Glover, Fred (1986), "Two algorithms for weighted matroid intersection", Mathematical Programming, 36 (1): 39–53, doi:10.1007/BF02591988, S2CID 34567631
^ Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki (2019-09-01). "Exact and approximation algorithms for weighted matroid intersection". 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), "A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision", 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-3, S2CID 245799113, retrieved 2022-11-28
^ Bérczi, Kristóf; Király, Tamás; Yamaguchi, Yutaro; Yokoi, Yu (2022-09-28). "Matroid Intersection under Restricted Oracles". arXiv:2209.14516 [cs.DS].
^ Welsh, D. J. A. (2010) [1976], Matroid Theory, Courier Dover Publications, p. 131, ISBN 9780486474397.
^ Lawler, Eugene L. (1976), "Chapter 9: The Matroid Parity Problem", Combinatorial Optimization: Networks and Matroids, New York: Holt, Rinehart and Winston, pp. 356–367, MR 0439106.
^ Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing, 11 (1): 184–190, doi:10.1137/0211014, MR 0646772.
^ Murota, Kazuo (1996-11-01). "Valuated Matroid Intersection I: Optimality Criteria". SIAM Journal on Discrete Mathematics. 9 (4): 545–561. doi:10.1137/S0895480195279994. ISSN 0895-4801.
^ Murota, Kazuo (November 1996). "Valuated Matroid Intersection II: Algorithms". SIAM Journal on Discrete Mathematics. 9 (4): 562–576. doi:10.1137/S0895480195280009. ISSN 0895-4801.

추가열람

Aigner, Martin; Dowling, Thomas (1971), "Matching theory for combinatorial geometries", Transactions of the American Mathematical Society, 158 (1): 231–245, doi:10.1090/S0002-9947-1971-0286689-5.
Frederickson, Greg N.; Srinivas, Mandayam A. (1989), "Algorithms and data structures for an expanded family of matroid intersection problems" (PDF), SIAM Journal on Computing, 18 (1): 112–138, doi:10.1137/0218008, archived from the original on September 22, 2017.
Gabow, Harold N.; Tarjan, Robert E. (1984), "Efficient algorithms for a family of matroid intersection problems", Journal of Algorithms, 5 (1): 80–131, doi:10.1016/0196-6774(84)90042-7..

[:0-1] Edmonds, Jack (1970), "Submodular functions, matroids, and certain polyhedra", in R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69–87M. Jünger et al. (Eds.): Edmonds, Jack (1970), "Submodular functions, matroids, and certain polyhedra", in R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69–87조합 최적화 (Edmonds Festschrift), LNCS 2570, pp. 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] Iri, Masao; Tomizawa, Nobuaki (1976). "An Algorithm for Finding an Optimal "Independent Assignment"". 日本オペレーションズ・リサーチ学会論文誌. 19 (1): 32–57. doi:10.15807/jorsj.19.32.

[4] Frank, András (1981), "A weighted matroid intersection algorithm", Journal of Algorithms, 2 (4): 328–336, doi:10.1016/0196-6774(81)90032-8

[5] Orlin, James B.; VandeVate, John; Management, Sloan School of (2012-06-07). "On a "primal" matroid intersection algorithm". {{cite journal}}:저널 요구사항 인용 journal=(도움말)

[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] Brezovec, Carl; Cornuéjols, Gérard; Glover, Fred (1986), "Two algorithms for weighted matroid intersection", Mathematical Programming, 36 (1): 39–53, doi:10.1007/BF02591988, S2CID 34567631

[8] Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki (2019-09-01). "Exact and approximation algorithms for weighted matroid intersection". 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), "A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision", 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-3, S2CID 245799113, retrieved 2022-11-28

[10] Bérczi, Kristóf; Király, Tamás; Yamaguchi, Yutaro; Yokoi, Yu (2022-09-28). "Matroid Intersection under Restricted Oracles". arXiv:2209.14516 [cs.DS].

[11] Welsh, D. J. A. (2010) [1976], Matroid Theory, Courier Dover Publications, p. 131, ISBN 9780486474397.

[12] Lawler, Eugene L. (1976), "Chapter 9: The Matroid Parity Problem", Combinatorial Optimization: Networks and Matroids, New York: Holt, Rinehart and Winston, pp. 356–367, MR 0439106.

[13] Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing, 11 (1): 184–190, doi:10.1137/0211014, MR 0646772.

[14] Murota, Kazuo (1996-11-01). "Valuated Matroid Intersection I: Optimality Criteria". SIAM Journal on Discrete Mathematics. 9 (4): 545–561. doi:10.1137/S0895480195279994. ISSN 0895-4801.

[15] Murota, Kazuo (November 1996). "Valuated Matroid Intersection II: Algorithms". SIAM Journal on Discrete Mathematics. 9 (4): 562–576. doi:10.1137/S0895480195280009. ISSN 0895-4801.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Search