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.

| cite | improve this answer | |

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.