Jun 30 2009
We don’t know a thing. It’s al…
We don’t know a thing. It’s all in the past now. Money changes everything: http://bit.ly/1zBrT
Jun 29 2009
Approximating Spanning Trees with Low Crossing Number
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 29 2009
The secret SODA submissions se…
The secret SODA submissions server is at http://soda10.cs.princeton.edu/.
Jun 26 2009
Public university and connections
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…
Jun 26 2009
Boruvka’s algorithm is from 19…
Boruvka’s algorithm is from 1926! http://en.wikipedia.org/wiki/Boruvka’s_algorithm
Jun 25 2009
I agree with Ahmadinejad – Oba…
I agree with Ahmadinejad – Obama must immediately stop oppressing, killing, and lying to the Iranian people: http://tinyurl.com/nn3nxu
Jun 23 2009
Recent talks
Next Page »