3-dimensional matching approximation algorithm (implementation details)

Problem Detail: 

I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below: How can I construct the maximum matching M_r in S_r in linear time in line 8?

$X, Y, Z $ are disjoint sets; a matching $M$ is a subset of $S$ s.t. no two triples in $M$ have the same coordinate at any dimension.

$ \text{Algorithm: unweighted 3-dimensional matching (2-approximation)} \\ \text{Input: a set $S\subseteq X \times Y \times Z$ of triples} \\ \text{Output: a matching 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

Asked By : Reibach

Answered By : Herm

We don't need the maximum matching, just one of cardinality $2$ if it exists.

Scan $S_r$ looking for a triple $T$ such that $\lvert T \cap \{a, b, c\}\rvert = 1$. If no such $T$ exists, then the maximum cardinality of a matching is clearly $1$. Otherwise, assume without loss of generality that $T = \{a, x, y\}$.

Scan $S_r$ again looking for a triple $U$ such that $T \cap U = \varnothing$. If no such $U$ exists, then every triple intersects both $\{a, b, c\}$ and $T$. For every $U \in S_r$, we have $\{a\} \subseteq U$ or $\{b, x\} \subseteq U$ or $\{b, y\} \subseteq U$ or $\{c, x\} \subseteq U$ or $\{c, y\} \subseteq U$.

There are several possibilities for a cardinality-$2$ matching $\{T_1, T_2\}$. There's an easy test for those of type $\{b, x\} \subseteq T_1$ and $\{c, y\} \subseteq T_2$. Similarly, $\{b, y\}$ and $\{c, x\}$. The only other types are the four like $\{a\} \subseteq T_1$ and $\{b, x\} \subseteq T_2$. To test for those, gather all triples of the form $\{b, x, z\} \in S_r$ and discard the ones in excess of three. Try each of the remainder against all possibilities containing $a$. The three $\{b, x, z\}$ candidates suffice because no triple containing neither $b$ nor $x$ intersects all three.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2571