Next: MINIMUM ARRAY PARTITION
Up: Weighted Set Problems
Previous: MAXIMUM CAPACITY REPRESENTATIVES
  Index
- INSTANCE:
Finite set A, size
for each
,
and an integer
.
- SOLUTION:
A partition of A into K disjoint sets
.
- MEASURE:
- Good News:
Approximable within 25/24 [111].
- Comment:
There are somewhat better approximation ratios for
[334].
- Garey and Johnson: SP19
Viggo Kann
1999-04-22