# Load balancing/partitioning with unknown weights

For a grid-based numerical simulation, I am looking for a load balancing/partitioning algorithm that not only distributes my grid elements, but also determines (approximates) their respective weights. Does anyone know of existing approaches for this problem or can give me some pointers into which kind of mathematical field I should be looking for a possible solution?

Details

Let's say I have $$N_e$$ grid elements $$e_i$$, each with a certain computational weight $$w_i$$. The $$w_i$$ are all within an order of magnitude, but I don't know their exact value a priori. The elements are now to be distributed among $$N_p$$ processes, preserving their order. I can only measure the cumulative weight of all elements on one process but not their individual contributions. However, I can repartition the grid multiple times to get multiple measurements with different decompositions.

What I am searching for is a method that lets me determine an estimate for the $$w_i$$ with a relatively low number of decompositions $$N_d$$. The numbers involved here are in the range of $$N_e = \mathcal{O}(10^9)$$, $$N_p = \mathcal{O}(10^5)$$, and $$N_d = \mathcal{O}(10^2)$$.