Next:
MINIMUM ARRAY PARTITION
Up:
Weighted Set Problems
Previous:
MAXIMUM CAPACITY REPRESENTATIVES
 
Index
M
INIMUM
S
UM OF
S
QUARES
I
NSTANCE:
Finite set
A
, size
for each
, and an integer
.
S
OLUTION:
A partition of
A
into
K
disjoint sets
.
M
EASURE:
Good News:
Approximable within 25/24 [
119
].
Comment:
There are somewhat better approximation ratios for
[
350
].
Garey and Johnson:
SP19
Viggo Kann
2000-03-20