3维匹配近似算法（实现详细信息）

Question

我有一个关于3维（未加权2-）近似算法的运行时实现问题：如何在第8行中的线性时间内构建S_R中的最大匹配M_R？

$ x，y，z $是不连接的集；匹配的$ m $是$ s $ st no $ m $的子集，$ m $在任何维度上具有相同的坐标。

$ text {算法：未加权的3维匹配（2- approximation）} text {input {input：a seet $ s subseteq x times y times y times y times y times z $ of Trieles} text {outption：autpti m in s} $

 1) construct maximal matching M in S;  
 2) change = TRUE;  
 3) while (change) {  
 4)   change = FALSE;  
 5)   for each triple (a,b,c) in M {  
 6)     M = M - {(a,b,c)};  
 7)     let S_r be the set of triples in S not contradicting M;  
 8)     construct a maximum matching M_r in S_r;  
 9)     if (M_r contains more than one triple) {  
10)       M = M \cup M_r;  
11)       change = TRUE;  
12)     } else {  
13)       M = M \union {(a,b,c)};  
14)     }  
15) }  

---

[1] http://faculty.cse.tamu.edu/chen/courses/cpsc669/2011/notes/ch9.pdf, ，p。 326

Answer 1

我们不需要最大的匹配，如果存在的话，只有基数$ 2 $。

扫描$ s_r $寻找三重$ t $，以便$ lvert t cap {a，b，c } rvert = 1 $。如果不存在这样的$ t $，那么匹配的最大基数显然为$ 1 $。否则，假设$ t = {a，x，y } $而不会损失一般性。

扫描$ s_r $再次寻找三重$ u $，以便$ t cap u = varnothing $。如果不存在这样的$ u $，则每个三重三重相交$ {a，b，c } $和$ t $。对于s_r $中的每一个$ u ，我们都有$ {a } subseteq u $或$ {b，x } subseteq u $或$ {b，y } {c，x } subseteq u $或$ {c，y } subseteq u $。

有几种可能性的基数 - $ 2 $匹配$ {t_1，t_2 } $。对于类型$ {b，x } subseteq t_1 $和$ {c，y } subseteq t_2 $的类型，有一个简单的测试。同样，$ {b，y } $和$ {c，x } $。唯一的其他类型是四种，例如$ {a } subseteq t_1 $和$ {b，x } subseteq t_2 $。要为这些测试，请在s_r $中收集$ {b，x，z } 表格的所有三元组，然后丢弃超过三个。尝试每个包含$ a $的所有可能性。这三个$ {b，x，z } $候选人足够了，因为没有包含$ b $的三重，也不包含$ x $，这三个都不相交。