Given a complete graph G=(V,E), a weight function on its edges, and a penalty function on its vertices, the penalized k-min-sum problem is the problem of finding a partition of V to k+1 sets, S1,...,Sk+1, minimizing , where for , and p(S)=[summation operator]i[set membership, variant]Spi. Our...