OPTIMAL PARTITIONS HAVING DISJOINT CONVEX AND CONIC HULLS

Let A1,...,A(n) be distinct k-dimensional vectors. We consider the pro blem of partitioning these vectors into m sets so as to maximize an ob jective which is a quasi-convex function of the sum of vectors in each set. We show that there exists an optimal partition whose sets have ( pairwise) disjoint conic hulls. We also show that if the number of vec tors in each of the sets is constrained, then a weaker conclusion hold s, namely, there exists an optimal partition whose sets have (pairwise ) disjoint convex hulls. The results rely on deriving necessary and su fficient conditions for a point to be an extreme point of a correspond ing polytope.