Next: MAXIMUM SET PACKING Up: Covering, Hitting, and Splitting Previous: Covering, Hitting, and Splitting Index

### MAXIMUM 3-DIMENSIONAL MATCHING

- INSTANCE: Set , where X, Y, and Z are disjoint.

- SOLUTION: A matching for T, i.e., a subset such that no elements in M agree in any coordinate.

- MEASURE: Cardinality of the matching, i.e., |M|.

- Good News: Approximable within 3/2 for any [250].

- Bad News: APX-complete [265].

- Comment: Transformation from MAXIMUM 3-SATISFIABILITY. In the weighted case, the problem is approximable within for any [29].

  Admits a PTAS for `planar' instances [365]. 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 [265]. The generalized Maximum k-Dimensional Matching problem is approximable within for any [250], 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 for some [452].

- Garey and Johnson: SP1

Next: MAXIMUM SET PACKING Up: Covering, Hitting, and Splitting Previous: Covering, Hitting, and Splitting Index