3-dimensionale algoritmo di corrispondenza approssimazione (dettagli di implementazione)

Question

Ho una domanda implementazione runtime per quanto riguarda il 3-dimensionale (non ponderata 2-) approssimazione algoritmo di seguito: Come posso costruire la massima corrispondenza M_r in S_r in tempo lineare in linea 8?

$ X, Y, Z $ sono insiemi disgiunti; un abbinamento $ M $ è un sottoinsieme di $ S $ S.T. no due triple in $ M $ hanno lo stesso coordinata, in qualsiasi dimensione.

$ \ Text {Algoritmo: non pesato corrispondenza 3-dimensionale (2-approssimazione)} \\ \ Text {Input: un insieme $ S \ subseteq X \ times Y \ times Z $ di triple} \\ \ Text {Output: un abbinamento 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 / corsi / cpsc669 / 2011 / Note / ch9.pdf , pag. 326

Answer 1

Non abbiamo bisogno della massima corrispondenza, solo una delle cardinalità $ 2 $ se esiste.

Scan $ S_r $ alla ricerca di una tripla $ T $ tale che $ \ lVert T \ cap \ {a, b, c \} \ rvert = 1 $. In assenza di tale $ T $ esiste, quindi la cardinalità massima di una corrispondenza è chiaramente $ 1 $. In caso contrario, assumere senza perdita di generalità che $ T = \ {a, x, y \} $.

Scan $ S_r $ di nuovo alla ricerca di una tripla $ U $ tale che $ T \ tappo U = \ varnothing $. In assenza di tale $ U $ esiste, poi ogni triple interseca sia $ \ {a, b, c \} $ e $ T $. Per ogni $ U \ in S_r $, abbiamo $ \ {a \} \ subseteq U $ o $ \ {b, x \} \ subseteq U $ o $ \ {b, y \} \ subseteq U $ o $ \ {c, x \} \ subseteq U $ o $ \ {c, y \} \ subseteq U $.

Ci sono diverse possibilità per una cardinality- $ 2 $ corrispondenza $ \ {T_1, T_2 \} $. C'è un test facile per quelli di tipo $ \ {b, x \} \ subseteq T_1 $ e $ \ {c, y \} \ subseteq T_2 $. Allo stesso modo, $ \ {b, y \} $ e $ \ {c, x \} $. Gli unici altri tipi sono i quattro come $ \ {a \} \ subseteq T_1 $ e $ \ {b, x \} \ subseteq T_2 $. Per di prova per chi, di raccogliere tutte le triple della forma $ \ {b, x, z \} \ in S_r $ e scartare quelle in eccesso di tre. Provare a effettuare il resto contro tutte le possibilità che contengono $ a $. I tre $ \ {b, x, z \} $ candidati bastano perché nessuno tripla contenente né $ b $ né $ x $ interseca tutti e tre.