三维匹配问题
 |
 | 此条目没有列出任何参考或来源。 (2012年11月2日) |
三维匹配（缩写3DM）是六个经典NP完全问题之一，是经典稳定婚姻问题的推广，婚姻问题是：有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格，问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚？
在三维匹配问题中，可以用集合，和对应于“三个”不同的性别，属于。用集合中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决，而3DM是NP完全的。
在数学学科的图论中，三维匹配是二分图匹配（也称为二维匹配）推广到三方超图，它由超边组成，每个超边包含 3 个顶点（而不是普通图中包含 2 个顶点的边）。
三维匹配是最早证明为NP困难之一的问题。
定义
[编辑]设 X、Y 和 Z 为有限集合，并设 T 为 X × Y × Z 的子集。也就是说，T 由三元组 (x, y, z) 组成，其中 x ∈ X，y ∈ Y，且 z ∈ Z。现在，如果以下条件成立，则 M ⊆ T 是一个三维匹配：对于任何两个不同的三元组 (x1, y1, z1) ∈ M 和 (x2, y2, z2) ∈ M，我们有 x1 ≠ x2，y1 ≠ y2，且 z1 ≠ z2。
示例
[编辑]右图说明了三维匹配。集合 X 用红色点标记，Y 用蓝色点标记，Z 用绿色点标记。图 (a) 显示了集合 T（灰色区域）。图 (b) 显示了 |M| = 2 的三维匹配 M，图 (c) 显示了 |M| = 3 的三维匹配 M。
图 (c) 中说明的匹配 M 是一个“最大三维匹配”，即它最大化 |M|。图 (b)–(c) 中说明的匹配是“极大三维匹配”，即它们不能通过添加来自 T 的更多元素来扩展。
与二分图匹配的比较
[编辑]可以用完全类似的方式定义“二维匹配”。设 X 和 Y 为有限集合，并设 T 为 X × Y 的子集。现在，如果以下条件成立，则 M ⊆ T 是一个二维匹配：对于任何两个不同的配对 (x1, y1) ∈ M 和 (x2, y2) ∈ M，我们有 x1 ≠ x2 且 y1 ≠ y2。
在二维匹配的情况下，集合 T 可以解释为二分图 G = (X, Y, T) 中边的集合；T 中的每条边都将 X 中的一个顶点连接到 Y 中的一个顶点。然后，二维匹配是图 G 中的一个匹配，即一组成对非相邻的边。
因此，三维匹配可以解释为匹配对超图的推广：集合 X、Y 和 Z 包含顶点，T 的每个元素都是一条超边，集合 M 由成对非相邻的边组成（没有共同顶点的边）。在二维匹配的情况下，我们有 Y = Z。
与Set packing 的比较
[编辑]三维匹配是Set packing的一个特例：我们可以将 T 的每个元素 (x, y, z) 解释为 X ∪ Y ∪ Z 的子集 {x, y, z}；那么，三维匹配 M 由成对不相交的子集组成。
判定问题
[编辑]在计算复杂性理论中，三维匹配是以下判定问题的名称：给定一个集合 T 和一个整数 k，判断是否存在一个三维匹配 M ⊆ T，使得 |M| ≥ k。
这个判定问题已知是NP完全的；是卡普的二十一个NP-完全问题之一。[1] 即使在 k = |X| = |Y| = |Z| 且每个元素最多包含在 3 个集合中，也就是说，当我们想要一个 3-正则超图中的完美匹配时，它也是 NP 完全的。[1][2][3] 在这种情况下，三维匹配不仅是一个Set packing，而且还是一个精确覆盖：集合 M 恰好覆盖 X、Y 和 Z 的每个元素一次。[4] 这个证明是通过从3SAT简化而来的。给定一个 3SAT 实例，我们构造一个 3DM 实例如下：[2][5]
对于每个变量 xi，都有一个形状像轮子的“变量 gadget”。它由重叠的三元组组成。三元组的数量是 xi 在公式中出现次数的两倍。恰好有两种方法可以覆盖 gadget 中的所有顶点：一种是选择所有偶数索引的三元组，另一种是选择所有奇数索引的三元组。这两种方法分别对应于将 xi 设置为“真”或“假”。 “真”选择在每个奇数索引的三元组中恰好留下一个未覆盖的顶点，而“假”选择在每个偶数索引的三元组中恰好留下一个未覆盖的顶点。
对于每个子句 xi u xj u xk，都有一个形状像玫瑰的“子句 gadget”。它由三个重叠的三元组组成，每个子句中的每个变量一个。它可以被覆盖，当且仅当至少一个节点被变量 gadget 的选择留下未覆盖。
由于可能留下两个或多个未覆盖的节点，我们还需要一个“垃圾收集 gadget”。它的形状像一朵更大的玫瑰。它由几个重叠的三元组组成，每个变量 gadget 中可能留下的每个未覆盖的顶点一个。此类 gadget 的数量被确定，以便只有在存在令人满意的分配时才能完全覆盖它们。
特例
[编辑]存在用于求解稠密超图中 3DM 的多项式时间算法。[6][7] 存在用于求解稠密超图中的3DM的多主题的时间间隔算法。 卡尔宾斯基, 鲁钦斯基 & 希曼斯卡 (2009) Keevash, Knox & Mycroft (2013)
优化问题
[编辑]“最大三维匹配”是最大的三维匹配。在计算复杂性理论中，这也是以下优化问题的名称：给定一个集合 T，找到一个最大化 |M| 的三维匹配 M ⊆ T。
由于上面描述的判定问题是 NP 完全的，因此这个优化问题是 NP困难 的，因此似乎没有多项式时间算法可以找到最大三维匹配。但是，存在有效率的多项式时间算法可以找到最大二分图匹配（最大二维匹配），例如霍普克罗夫特-卡普算法。
近似算法
[编辑]对于三维匹配，有一个非常简单的多项式时间 3-近似算法：找到任何极大三维匹配。[8] 就像极大匹配在最大匹配的 2 倍因子内一样，[9] 极大三维匹配在最大三维匹配的 3 倍因子内。
对于任何常量 ε > 0，都有一个用于三维匹配的多项式时间 (4/3 + ε)-近似算法。[10]
但是，获得更好的近似因子可能很难：这个问题是 APX完全 的，也就是说，很难在某个常量内近似。[11][12][8]
对于最大 3-d 匹配，很难实现 95/94 的近似因子，对于最大 4-d 匹配，很难实现 48/47 的近似因子。即使限制为每个元素恰好出现两次的实例，这种困难仍然存在。[13]
并发算法
[编辑]在大规模并发通信模型中，存在各种用于 3-d 匹配的算法。[14]
参见
[编辑]注释
[编辑]- ^ 1.0 1.1 Karp (1972).
- ^ 2.0 2.1 Template:Garey-Johnson, 第 3.1 节和附录 A.3.1 中的问题 SP1。
- ^ Korte, Bernhard; Vygen, Jens, Combinatorial Optimization: Theory and Algorithms 3rd, Springer, 2006, 第 15.5 节。
- ^ Papadimitriou & Steiglitz (1998), 第 15.7 节。
- ^ Demaine, Erik. 16. Complexity: P, NP, NP-completeness, Reductions. YouTube. 2016.
- ^ Karpinski, Rucinski & Szymanska (2009)
- ^ Keevash, Knox & Mycroft (2013)
- ^ 8.0 8.1 Kann (1991)
- ^ 匹配 (图论)#性质.
- ^ Cygan, Marek. Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. 2013: 509–518. Bibcode:2013arXiv1304.1424C. ISBN 978-0-7695-5135-7. S2CID 14160646. arXiv:1304.1424
. doi:10.1109/FOCS.2013.61.
- ^ Crescenzi et al. (2000).
- ^ Ausiello et al. (2003), 附录 B 中的问题 SP1。
- ^ Chlebík, Miroslav; Chlebíková, Janka. Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science. Foundations of Computation Theory (FCT 2003). 2006-04-04, 354 (3): 320–338. ISSN 0304-3975. doi:10.1016/j.tcs.2005.11.029 （英语）.
- ^ Hanguir, Oussama; Stein, Clifford. Distributed Algorithms for Matching in Hypergraphs. 2020-09-21. arXiv:2009.09605 [cs.DS].
参考文献
[编辑]- Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003.
- Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard, Maximum 3-dimensional matching, A Compendium of NP Optimization Problems, 2000.
- Kann, Viggo, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, 1991, 37 (1): 27–35, doi:10.1016/0020-0190(91)90246-E.
- Karp, Richard M., Reducibility among combinatorial problems, Miller, Raymond E.; Thatcher, James W. (编), Complexity of Computer Computations, Plenum: 85–103, 1972.
- Karpinski, Marek; Rucinski, Andrzej; Szymanska, Edyta, The Complexity of Perfect Matching Problems on Dense Hypergraphs, ISAAC '09 Proceedings of the 20th International Symposium on Algorithms, Lecture Notes in Computer Science, 2009, 5878: 626–636, ISBN 978-3-642-10630-9, doi:10.1007/978-3-642-10631-6_64.
- Keevash, Peter; Knox, Fiachra; Mycroft, Richard, Polynomial-time perfect matchings in dense hypergraphs, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing: 311–320, 2013, Bibcode:2013arXiv1307.2608K, ISBN 9781450320290, S2CID 5393523, arXiv:1307.2608 , doi:10.1145/2488608.2488647.
- Papadimitriou, Christos H.; Steiglitz, Kenneth, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.