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

- 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 [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
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

*Viggo Kann*

*2000-03-20*