tag:blogger.com,1999:blog-8890204.post9171688981508624965..comments2024-03-10T05:26:42.148-04:00Comments on My Biased Coin: Bertinoro, Day 2Michael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8890204.post-11110381331623420672010-06-03T12:27:37.904-04:002010-06-03T12:27:37.904-04:00Hello,
I have an interesting problem that I'm...Hello,<br /><br />I have an interesting problem that I'm almost sure has been solved already. I don't have a background in networks or load-balancing, so I thought I'd post it here. <br /><br />Let's say we have K bins (Y_1,...,Y_K) and we need to distribute N (where N>K) balls to these bins. The balls each of an associated weight (X_1,...,X_N). What's the fastest algorithm to ensure that we have "load-balanced." I'm not sure what a good metric for load-balancing is, but my intuition says something like the variance of the weights across all bins. <br /><br />My apologies if this is trivial. My current algorithm is greedy; distribute the first K balls to the K bins, then continue to distribute by taking the next ball and putting it in the lowest-weighted bin. I haven't been able to prove if this is optimal or not.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-13357375416064664382010-06-02T08:03:03.946-04:002010-06-02T08:03:03.946-04:00Is there going to be a proceedings for this confer...Is there going to be a proceedings for this conference?Anonymousnoreply@blogger.com