Given the complete graph on n vertices. Each vertex and each edge has a positive weight associated with it. What is desired is to partition the vertices into parts so that the sum of the weights of the vertices of any part is less or equal to the minimum of the weights of edges connecting vertices in that part. What is the minimum size of such a partition?
Has anyone seen this before?
