Optimal partitions having disjoint convex and conic hulls

LetA ¹,,A ⁿ be distinctk-dimensional vectors. We consider the problem of partitioning these vectors intom sets so as to maximize an objective 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 vectors in each of the sets is constrained, then a weaker conclusion holds, namely, there exists an optimal partition whose sets have (pairwise) disjoint convex hulls. The results rely on deriving necessary and sufficient conditions for a point to be an extreme point of a corresponding polytope.Research of this author was partially supported by NSF Grant ECS-83-10213 and by a Grant for the Promotion of Research at the Technion.