<p>This problem is called <a href="https://en.wikipedia.org/wiki/Bin_covering_problem" rel="nofollow noreferrer">bin covering</a>. 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 <span class="math-container">$(1-\epsilon)\mathrm{OPT}-O(1)$</span> bins). See e.g. &quot;Better approximation algorithms for bin covering&quot;, Csirik, Johnson, and Kenyon, SODA 2001, or &quot;An asymptotic fully polynomial time approximation scheme for bin covering&quot;, Jansen and Solis-Oba, TCS 2003.</p>

CC BY-SA 4.0
2018-05-02T07:29:39.727Z
2021-10-30T20:03:16.277Z
2021-10-30T20:03:16.277Z
David Eppstein
<p>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?</p>

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

CC BY-SA 3.0
2018-05-01T20:44:35.900Z
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?
daniello
CC BY-SA 3.0
2018-05-01T20:48:26.070Z
@daniello No, to be honest, I've simply overlooked this simple reduction.
domotorp
CC BY-SA 3.0
2018-05-01T21:16:55.980Z
Ok. Also, when the number of bins is part of the input the problem is strongly NP-complete by reduction from 3-partition.
daniello
CC BY-SA 4.0
2021-10-29T09:02:12.043Z
https://en.wikipedia.org/wiki/Bin_covering_problem
Erel Segal-Halevi
<ds.algorithms><integer-programming>
Anti bin packing
domotorp
# Anti bin packing

(Asked by: username_0 on 2018-05-01)

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!

**Tags:** ds.algorithms, integer-programming
> **Comments:**
> **username_1**: 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?  
> **username_0**: @daniello No, to be honest, I've simply overlooked this simple reduction.  
> **username_1**: Ok. Also, when the number of bins is part of the input the problem is strongly NP-complete by reduction from 3-partition.  
> **username_2**: https://en.wikipedia.org/wiki/Bin_covering_problem  

---

## 1 answers

### Answer by username_3 on 2018-05-02. Score: 11 | Accepted answer

This problem is called [bin covering](https://en.wikipedia.org/wiki/Bin_covering_problem). 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.


---

