Questions tagged [balls-and-bins]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
13
votes
1answer
949 views

Use minimum number of swaps so each bin contains balls of the same color

There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=\sum_{i=1}^n a_i$. A swap is take a ball from one bin and swap with a ball ...
12
votes
1answer
447 views

Filling bins with pairs of balls

A bin is called full if it contains at least $k$ balls. Our goal is to make as many bins as possible full. In the simplest scenario, we are given $n$ balls and may arrange them arbitrarily. In that ...
2
votes
1answer
129 views

Finding a specific “balls-into-bins” partition given its index in the lexicographical ordering

Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins. Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in $\{0,...
2
votes
1answer
1k views

Load balancing. Why not use priority queues?

I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize ...
1
vote
1answer
90 views

Assigning $m$ balls to $n$ buckets - recursive algorithm

I came across the following problem and the answer to that problem: Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, ...
1
vote
0answers
38 views

Algorithms of placing N weighted balls into M uniform bins while striving for balanced weight?

Suppose there're $N$ weighted balls and $M$ equal weight bins, it's guaranteed at least one placement exists that all the balls can be placed into bins. What's the right algorithm to achieve a well-...