Sphere-separable partitions of multi-parameter elements
We show the optimality of sphere-separable partitions for problems where n n vectors in d d -dimensional space are to be partitioned into p p categories to minimize a cost function which is dependent in the sum of the vectors in each category; the sum of the squares of their Euclidean norms; and the number of elements in each category. We further show that the number of these partitions is polynomial in n n . These results broaden the class of partition problems for which an optimal solution is guaranteed within a prescribed set whose size is polynomially bounded in n n . Applications of the results are demonstrated through examples.
partitions polynomial bounds combinatorial optimization separation