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

  • $\begingroup$ Welcome! "Implementation details" is something this site is not about, but it seems as if you were after an algorithm? $\endgroup$ – Raphael Jul 1 '12 at 21:45
  • $\begingroup$ Well, I want to implement this algorithm in $O(n^3)$. $\endgroup$ – Reibach Jul 1 '12 at 21:48

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.

| cite | improve this answer | |
  • $\begingroup$ Why do we only need to consider matchings of cardinality 2? And why is it that if no $T \neq \{a,b,c\}$ exists such that $|T \cap \{a,b,c\}| = 1$ that the cardinality of the matching is 1? $\endgroup$ – Reibach Jul 3 '12 at 21:55
  • $\begingroup$ "Why do we only need to consider matchings of cardinality 2?" It suffices either to verify that $S_r$ is maximum or grow the matching. "And why is it that..." If every triple has two elements in common with {a, b, c}, then every pair of triples has at least one element in common by the pigeonhole principle. $\endgroup$ – Herm Jul 4 '12 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.