Timeline for Bin packing first-fit problem in $O(n \log n)$ time
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2019 at 15:40 | vote | accept | Andrew | ||
| May 2, 2019 at 13:51 | answer | added | George Vidalakis | timeline score: 4 | |
| May 2, 2019 at 10:10 | comment | added | gnasher729 | The problem is implementing “first fit” in O(n log n). | |
| May 2, 2019 at 9:13 | comment | added | xskxzr | What's the target of your problem? Minimize the number of bins? Also, do you mean the objects arrive in an online fashion, and when an object arrives, the algorithm must determine immediately into which bin to insert it? | |
| May 2, 2019 at 9:07 | comment | added | Discrete lizard♦ | Your current algorithm is incorrect: if sum<nOfBins, it could still be nessecary to pick a new bin. For example, take the weights $(0.7,0.5,0.6)$. When inserting $0.6$, the total sum is $1.8<2$, but we still need at least 3 bins. You will have to do some form of 'searching' for the right bin to insert, which is where the extra log factor will come from. | |
| May 2, 2019 at 9:01 | history | asked | Andrew | CC BY-SA 4.0 |