Databases
StackOverflow2013
Postsdbo
PODistributing stones into buckets (not trivial) / Integer Bin Packing Upper bound
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODistributing stones into buckets (not trivial) / Integer Bin Packing Upper bound
    primarykey
    data
    text
    <p>Suppose you have k stones and m stone types You have f1 stones from the first type, f2 from the second and so on.</p> <p>(i.e. sum(f_i) = k). </p> <p>In addition, we are given a positive integer r.</p> <p>What is the minimal number of buckets needed, such that we could distribute the stone types into buckets where the size of every bucket is no more than r? (We also know that for every i, f_i &lt;= r).</p> <p>This question is actually some kind of bin packing, so I'm not sure it has an exact answer but can we give it an upper bound?</p> <p>An example of a trivial upper bound is m, as this will allow us to pack each stone type in his own bucket.</p> <p>An example of a bound which doesn't work is k/r. The reason is that if k=9, r=3 and we have 5 stone types, f1 = 2, f2 = 2, f3 = 2, f4 = 2, f5=1,</p> <p>Then no matter how we partition the stone types, there has to be a bucket of size >= 4.</p> <p><strong>All stones from the same type has to go to the same bucket.</strong></p> <p>Any suggestions :) ?</p> <p>EDIT: m and the f_i's are unknown, and I'm looking for a bound which enables me to distribute the stones for all (m,f_i's) combination.</p> <p>Another example: Suppose that r = 3. I'll prove that k/2 buckets are enough:</p> <p>Let's denote by x the number of types for which there are 3 stones. y will denote the number of type from which there are exactly 2 stones, and z will the denote the number of single-stone types.</p> <p>By definition: 3x + 2y + z = k. We can allocate x buckets for the 3-stones types.</p> <p>If (y > z) {first case}: Fit one of the y types, together with one of the z types in a bucket {we have z such buckets}.</p> <p>Fit the rest of the y types one at a bucket.</p> <p>Since y > z we have used exactly x+y buckets, and since 3x + 2y + z = k => x+y &lt;= k/2.</p> <p>If (z >= y) {second case}: It's easy to see that we can fit all stones in k/3 buckets (every bucket can be full, containing exactly 3 stones).</p> <p>Also, for r=3, this bound it tight (if x=z=0 and y=k/2, then we need exactly k/2 buckets).</p> <p>Now the question is: does the k/2 buckets bound hold for all r values?</p> <p>I can show that a lower bound (i.e. a tight instance) of 2k/(r+1) buckets, but it's pretty far from k/2. Can anyone tighten the bound?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USuser3095429
    1. USuser3095429
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PODistributing stones into buckets (not trivial) / Integer Bin Packing Upper bound
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. PODistributing stones into buckets (not trivial) / Integer Bin Packing Upper bound
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAre stones of the same type required to go into the same bucket?
      singulars
      1. PODistributing stones into buckets (not trivial) / Integer Bin Packing Upper bound
      1. USAndrey Mishchenko
    2. COOr on the contrary stones of same type can't go into single bucket?
      singulars
      1. PODistributing stones into buckets (not trivial) / Integer Bin Packing Upper bound
      1. USSuor
    3. COI have to say it is pretty annoying that such an obvious question was not addressed up-front, when clearly the OP is assuming either my constraint or yours (@Suor), or some crazy constraint.
      singulars
      1. PODistributing stones into buckets (not trivial) / Integer Bin Packing Upper bound
      1. USAndrey Mishchenko
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload