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 '18 at 20:44
  • $\begingroup$ @daniello No, to be honest, I've simply overlooked this simple reduction. $\endgroup$ – domotorp May 1 '18 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 '18 at 21:16

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

