Vanity of Vanities, all is Vanity

Obama is a jack of all trades, master of none.

I thought it was bliss, but it was just my spam filter marking all my emails as spam.

Excellent: The quiet duel.

Saw the movie Slumdog Millionaire. I liked the photography, and the acting (especially of Anil Kapoor) was good at times, but the rest was unexciting.

I liked this movie: the closet.

It turns out that there is no such thing as neoconservativism. It was just a bad dream.

Boris Aronov, Esther Ezra and Micha Sharir, have a nice upcoming STOC paper, showing how to improve set-cover in certain geometric settings. Here, you have a set of points you need to cover by given regions in the plane (say fat triangles), and you would like to compute the minimum cardinality set of regions covering the points. Clarkson and Varadarajan showed that if the union complexity is near linear, then one can get an improved approximation. Thus, for fat triangles you get log(log(Opt)) approximation. The new paper shows that by doing a slight over-sampling, one can reduce the covering size by a log(linear union complexity overheard). Formally, if the union complexity of k regions is O(k * beta(k)), then you get a set cover of size O( Opt* log(beta(Opt))). (This paper also contain other results, using similar ideas in a more involved fashion for the dual settings of boxes and points.)

As such, for covering points by a given set of fat triangles, the new paper provides a cover by a set of size O(opt* log log log Opt).

This basic observation is simple but was missed by people working on this kind of problems (including myself). An interesting question is where else this over-sampling idea can be used?

June 11, 2009
University of Aarhus, Denmark
In connection with SoCG’09 and organized by
Center for Massive Data Algorithmics (MADALGO)

Call for papers.

North Dakota House Gives Fertilized Eggs Human Status. Requires that when refering to them, one calls them “Mr Egg”.

Its bloody cold again. UIUC needs a campus in Barbados.