Content deleted Content added
Citation bot (talk | contribs) Alter: template type, journal. Add: doi, volume, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 577/1776 |
m →The integral LP: Adding web.archive.org links for citations with url-status=live Category:CS1_maint:_url-status |
||
Line 7:
In the [[bin packing|bin packing problem]], there are ''n'' items with different sizes. The goal is to pack the items into a minimum number of bins, where each bin can contain at most ''B''. A ''feasible configuration'' is a set of sizes with a sum of at most ''B''.
* ''Example'':<ref name=":2">{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3|url-status=live|website=Coursera|archive-url=https://web.archive.org/web/20210715093252/https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3 |archive-date=2021-07-15 }}</ref> suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and ''B''=12. Then the possible configurations are: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. If we had only three items of size 3, then we could not use the 3333 configuration.
Denote by ''S'' the set of different sizes (and their number). Denote by ''C'' the set of different configurations (and their number). For each size ''s'' in ''S'' and configuration ''c'' in ''C'', denote:
| |||