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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.