Next: MINIMUM 3-DIMENSIONAL ASSIGNMENT
Up: Weighted Set Problems
Previous: Weighted Set Problems
  Index
- INSTANCE:
Finite set A and a size
for each
,
element
,
and a subset
.
- SOLUTION:
A partition of A, i.e., a subset
such that
.
- MEASURE:
Number of elements from S on the same side of the partition as a0.
- Bad News:
Not approximable within
for some
[452].
- Garey and Johnson: Similar to SP12
Viggo Kann
1999-04-22