MAXIMUM 3-DIMENSIONAL MATCHING

• INSTANCE: Set $T\subseteq X\times Y\times Z$, where X, Y, and Z are disjoint.
• SOLUTION: A matching for T, i.e., a subset $M\subseteq T$ such that no elements in M agree in any coordinate.
• MEASURE: Cardinality of the matching, i.e., $\vert M\vert$.

  
  

• Good News: Approximable within 3/2$+\varepsilon$ for any $\varepsilon >0$ [265].
• Bad News: APX-complete [280].
• Comment: Transformation from MAXIMUM 3-SATISFIABILITY. In the weighted case, the problem is approximable within $2+\varepsilon$ for any $\varepsilon >0$ [30]. Admits a PTAS for `planar' instances [386]. Variation in which the number of occurrences of any element in X, Y or Z is bounded by a constant B is APX-complete for $B \ge 3$ [280]. The generalized Maximum k-Dimensional Matching problem is approximable within $k/2+\varepsilon$ for any $\varepsilon >0$ [265], and within 2(k+1)/3 in the weighted case. The constrained variation in which the input is extended with a subset S of T, and the problem is to find the 3-dimensional matching that contains the largest number of elements from S, is not approximable within $\vert T\vert^{\varepsilon }$ for some $\varepsilon >0$ [476].
• Garey and Johnson: SP1