23
Oct

HItler’s Steiner Forest Algorithm


The Algorithms Conference was announced last week. It is going to be held in Berlin here and Knuth is visiting here. There will also be all those blog-writing Complexity theorists coming to present their new results showing some quantum computers. That’s OK, the Steiner Forest Problem will hold them up. Mein Fuhrer, Steiner .. Steiner Forest was solved some time ago by Williamson. It is a 2 approximation using LP Duality. Everyone who knows LP Complimentary slackness stay here The problem was supposed to be unsolvable! The whole Steiner thing was god damn NP complete. NP COMPLETE! Now you tell me they have already solved it using LP Duality. … I spent a damn year working on it. A WHOLE DAMN YEAR I tried every damn trick in Knuth, and nothing worked.
Trying to formulate Linear Programming equations But i couldnt find the dual solution. Mein Fuhrer, Ive looked at the Steiner approximate algorithm and it isnt all that hard. Just 2 pages. STFU you moron. Have you even looked at those damn LP’s and those stupid constraints. Mein Fuhrer, if you’d just read Vazirani I hate Vazirani. With those short chapters and open problems as exercises. Bloody Indian! Springer didnt even publish MY book. Mein Kamph And the copy i have is some cheap indian reprint.
00:01:56.000,00:01:58,000
Its not even Hardbound! I tried every possible LP relaxation technique. All i could come up with was a K-approximate solution. Not even a 3-approximate solution. I couldnt even prove it completely. My proof was WRONG. The journal rejected my paper the last time because they couldnt understand the proof. I even tried Science and Nature. WHat do they jews think, they can come up with some complicated LP and relax it and keep raising some stupid subsets and get all tight. I might as well move to some other research area in that case,
with all these jewish approximation algorithm swine. That steiner troubles me too much. Who in their right mind would consider all the subsets as constraints! And those nonsense Active Sets. And what is with all that reverse delete step anyways. Its supposed to be a fucking FOREST.

00:02:43.000,00:02:44.600
Who will ensure that it remains a friggin tree huh? You cant just do a reverse delete and hope it just destroys your cycles. Thats it ive had enough of Steiner. What next, will they even solve the prize collecting Steiner Forest problem without me now? Bloody jews! Its okay, we’ll give him an easy midsem to crack I remember when i proved the Steiner Tree 2 approximation. It was so simple and elegant I was a genius then. Now i cant prove anything anymore. I give up. Tell vazirani that i will cite his work now and try to find some other problem, and finally some research papers in FOCS and STOC And get me the mid-sem solution.

Tags: , , , , , ,

One Comment

  • Abby Sack says:

    I'm trying to compute the minimum cost of a Steiner Forest right now with the approximation algorithm and I know how he feels.

Leave a Reply

Your email address will not be published. Required fields are marked *