Sariel’s blog
: (0): Iran desperately looking for fight with outside: arresting UK embassy workers, etc. Solution: UK sends all perisoners as diplomats to Iran.
Jul 02 2009
At the sight of the still intact city, he remembered his great international precursors and set the whole place on fire with his artillery in order that those who came after him might work off their excess energies in rebuilding.
— The tin drum, Gunter Grass
June 30, 2009: (0): We don't know a thing. It's all in the past now. Money changes everything: http://bit.ly/1zBrT
: (0): @geomblog: Yeh, you are right. I am using Jaunty...
June 29, 2009: (0): Just biked 19 miles to St. Joseph and back. Tired.
Jun 29 2009
I just posted online my SODA submission. Here is the abstract:
We present a linear programming based algorithm for computing a spanning tree T of a set P of n points in the Rd, such that its crossing number is O(min( t log n, n1-1/d)), where t the minimum crossing number of any spanning tree of P. This is the first guaranteed approximation algorithm for this problem. We provide a similar approximation algorithm for the more general settings of building a spanning tree for a set system with bounded VC dimension.
Our approach replaces the reweighting technique previously used in computing such spanning trees.
I will probably update the writeup in the next few days. Any comments would be appriciated.
Jun 26 2009
There is a story unfolding about clouted students getting accepted to UIUC. It is kind of unavoidable in public system, and the number of students accepted in this way is so small that it did not compromise UIUC. But this is still not a happy story…
Private universities do it too, but at least they get paid for it in advance…