I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but couldn't find something. Thanks for the help!

You have n baskets and m cats (m >> n). The cats don't like each other, H_{ij} denotes how much cat i hates cat j (H_{ji} = H_{ij}). Each basket b has a capacity C_b and each cat c needs space C_c.

How can you minimize the sum over the H_{ij} of all cat pairs (i,j) that are assigned to the same basket? Every cat needs to be assigned to a basket.

  • $\begingroup$ This problem is NP-hard. Let $n=2$, $\frac {C_b} {C_c} = \frac m2$ (i.e. we need to place exactly half of cats into each basket). Think about your problem as a graph: $H_{ij}$ is a weight of edge between cats. So, you want to partition the cats into $2$ equal-sized groups so that the weight of edges inside each group is minimized. Equivalently, the weight of edges between the groups should be maximized. This is known as "Max Bisection" and is NP-hard (see e.g. "Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection", page 3) $\endgroup$ – user114966 Feb 22 at 7:58

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.