Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Balls into Bins via Local Search   We propose a natural process for allocating n balls into n bins that are
organized as the vertices of an undirected graph G. Each ball first chooses a
vertex u in G uniformly at random. Then the ball performs a local search in G
starting from u until it reaches a vertex with local minimum load, where the
ball is finally placed on. In our main result, we prove that this process
yields a maximum load of only \Theta(\log \log n) on expander graphs. In
addition, we show that for d-dimensional grids the maximum load is
\Theta\Big(\big(\frac{\log n}{\log \log n}\big)^{\frac{1}{d+1}}\Big). Finally,
for almost regular graphs with minimum degree \Omega(\log n), we prove that the
maximum load is constant and also reveal a fundamental difference between
random and arbitrary tie-breaking rules.

0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
26
The categories of this paper are: bayes-an
33
The categories of this paper are: plasm-ph
27
The categories of this paper are: comp-gas
8
The categories of this paper are: hep-ex
15
The categories of this paper are: nucl-ex
19
The categories of this paper are: eess
30
The categories of this paper are: q-alg
32
The categories of this paper are: atom-ph
3
The categories of this paper are: physics
17
The categories of this paper are: q-fin
11
The categories of this paper are: hep-lat
16
The categories of this paper are: stat
9
The categories of this paper are: nlin
24
The categories of this paper are: dg-ga