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