MINIMUM 3-DIMENSIONAL ASSIGNMENT

• INSTANCE: Three sets X, Y, and W and a cost function $c:X \times Y \times W \rightarrow N$.
• SOLUTION: An assignment A, i.e., a subset $A \subseteq X \times Y \times W$ such that every element of $X \cup Y \cup W$ belongs to exactly one triple in A.
• MEASURE: The cost of the assignment, i.e., $\sum_{(x,y,w) \in A}c(x,y,w)$.

  
  

• Bad News: Not in APX [124].
• Comment: The negative result holds even if c is either defined as c(x,y,w) = d(x,y)+d(x,w)+d(y,w) or defined as $c(x,y,w) = \min\{d(x,y)+d(x,w), d(x,y)+d(y,w), d(x,w)+d(y,w)\}$ where d is any distance function. In these cases, however, the problem is approximable within 4/3 if d satisfies the triangle inequality. Similar results hold for the k-dimensional problem [54].
• Garey and Johnson: Weighted version of SP2