Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

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

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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? –  Reibach Jul 3 '12 at 21:55
    
"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. –  Herm Jul 4 '12 at 2:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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