I have a (practically) unlimited amount of McDonald's coupons that I can use only if I shop for at least 1 money. Thus I want to partition my family's meal into as many parts as possible that all value at least 1. What is known about the complexity of this problem?

ps. Prices are typically long numbers, so don't suppose that they are given in unary!

  • 5
    $\begingroup$ It is NP-complete already for two bins because partitioning integers into 2 sets with equal sum is NP-complete. Were you looking for some approximation results? $\endgroup$
    – daniello
    May 1, 2018 at 20:44
  • $\begingroup$ @daniello No, to be honest, I've simply overlooked this simple reduction. $\endgroup$
    – domotorp
    May 1, 2018 at 20:48
  • $\begingroup$ Ok. Also, when the number of bins is part of the input the problem is strongly NP-complete by reduction from 3-partition. $\endgroup$
    – daniello
    May 1, 2018 at 21:16
  • $\begingroup$ en.wikipedia.org/wiki/Bin_covering_problem $\endgroup$ Oct 29, 2021 at 9:02

1 Answer 1


This problem is called bin covering. It's NP-hard and hard to approximate to better than a factor of two by an easy reduction from subset sum but has an asymptotic approximation scheme (i.e. one that fills $(1-\epsilon)\mathrm{OPT}-O(1)$ bins). See e.g. "Better approximation algorithms for bin covering", Csirik, Johnson, and Kenyon, SODA 2001, or "An asymptotic fully polynomial time approximation scheme for bin covering", Jansen and Solis-Oba, TCS 2003.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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