"Balls and Bins?", you ask, "Is there anything left to prove there?" Surprisingly, there are really natural questions that are open. Today I want to talk about one such question. First a quick primer. Balls and Bins processes model randomized allocations processes, used in hashing or more general load balancing schemes. Suppose that I have … Continue reading Balls and Bins on Graphs
Author: Kunal Talwar
Maximizing Submodular Functions (Part 2)
Continuing on my last post, today I will talk about recent work by Niv Buchbinder, Moran Feldman, Seffi Naor, and Roy Schwartz that gives a simple 1/2 approximation to the (unconstrained) submodular maximization problem, matching the hardness. Do see the paper (which should be available in a couple of weeks) for full details. Apologies in … Continue reading Maximizing Submodular Functions (Part 2)
Maximizing Submodular Functions (Part 1)
In this post and the next, I will talk about the problem of maximizing a submodular function. Submodularity is a natural property of set functions, that captures the diminishing returns property. Formally, let $latex f$ be a set function $latex f : 2^{U} \rightarrow \Re$, and let us assume that $latex U=[n]$. Then $latex f$ … Continue reading Maximizing Submodular Functions (Part 1)
