Next: MAXIMUM CAPACITY REPRESENTATIVES Up: Weighted Set Problems Previous: MAXIMUM CONSTRAINED PARTITION Index

### MINIMUM 3-DIMENSIONAL ASSIGNMENT

- INSTANCE: Three sets X, Y, and W and a cost function .

- SOLUTION: An assignment A, i.e., a subset such that every element of belongs to exactly one triple in A.

- MEASURE: The cost of the assignment, i.e., .

- Bad News: Not in APX [116].

- 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 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 [51].

- Garey and Johnson: Weighted version of SP2