MINIMUM SUM OF SQUARES

Next: MINIMUM ARRAY PARTITION Up: Weighted Set Problems Previous: MAXIMUM CAPACITY REPRESENTATIVES Index

INSTANCE: Finite set A, size $s(a)\in Z^+$ for each $a\in A$ , and an integer $K\ge 2$ .
SOLUTION: A partition of A into K disjoint sets $A_1, A_2,\ldots,A_K$ .
MEASURE:

$\begin{displaymath}\sum_{i=1}{K}\left(\sum_{a\in A_i} s(a)\right)^2.\end{displaymath}$
Good News: Approximable within 25/24 [119].
Comment: There are somewhat better approximation ratios for $K\hbox{ mod }5\ne 0$ [350].
Garey and Johnson: SP19

Viggo Kann
2000-03-20