Bertinoro is a really beautiful city. I just felt like saying that.
Today's talks: Geppino Pucci talked about Bluetooth networks, modeled as a variation of random geometric networks (points randomly distributed in the plane, connections to points within some radius, with Bluetooth you only connect to a bounded-size random subset of your neighbors) -- talk based on the ESA 2009 paper I believe. Rasmus Pagh talked about data mining (here's one of his papers on the subject), Graham Cormode talked about streaming verification of massive computations covering several of his recent papers on the theme (including this one), Andrew McGregor talked further about stream computations and "detecting dubious data structures" -- starting with how do you check in small space from the transcript of operations that your priority queue performs correctly given that is starts and ends empty (paper here), Tamas Sarlos talked about sparse random projection (paper will be at STOC next week), and Gagan Aggarwal talked about weighted online bipartite matching (generalizing the well-known KVV algorithm for online bipartite matching).
Sadly, the rest of the talks will have to go unblogged (by me at least) -- I'm leaving the workshop unreasonably early in order to get a few days of home time before STOC/EC/ISIT. See you all there...
Subscribe to:
Post Comments (Atom)
2 comments:
Is there going to be a proceedings for this conference?
Hello,
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.
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.
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.
Post a Comment