0
$\begingroup$

There is a list of objects. Each object cannot be in a bin with some other objects. How can I find the minimum number of bins required to hold all the objects (and the objects in them)?

My current algorithm:

For each object in the list, see if any of the currently existing bins will hold it. If yes, stick it in the first bin we come to that will hold it. If we exhaust the list of bins without finding a bin, create a new bin and stick the object into it.

Will this algorithm find the minimum number of bins? If not, what algorithm will (NP-hard algorithms OK: I have only about 12 objects)?

Feel free to add any tags you think appropriate - I'm not sure which one is

$\endgroup$
1
$\begingroup$

This is the clique cover problem in disguise, and finding an optimal solution NP-hard.

$\endgroup$
  • $\begingroup$ Any better algorithm than just brute-forcing it? $\endgroup$ – dpdt Jan 23 '18 at 22:45
  • $\begingroup$ @dpdt It's all about what trade-offs you're willing to make. I think greedily removing a maximal clique (which can be found efficiently) should give pretty good results. Your algorithm should be acceptable most of the time as well. If you insist on only having the optimal solution you're probably going to have to dive into some papers to find something that finishes computing for anything but the smallest cases at all. $\endgroup$ – orlp Jan 23 '18 at 22:51
  • $\begingroup$ The problem is NP-hard, not the algorithm. $\endgroup$ – Andrew Au Jan 24 '18 at 7:06
0
$\begingroup$

This problem can also be viewed as a graph coloring problem. You basically have a graph of objects, and each objects linked together must have different colors (i.e going to different bins)

In practice, some simple search (such as simulated annealing) is going to give you a pretty good solution for graph coloring. If you insist on the smallest number of bins, you can try constraint programming or similar exact solution techniques.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.