We have given to the students a task to promote algorithms on the web. This is what came up:
Click here for a version in polish.
Banach's Algorithmic Corner
University of Warsaw
We have given to the students a task to promote algorithms on the web. This is what came up:
Click here for a version in polish.
very good!
steiner wymiata!
The line "Do you know that third reich is a euclidean space", while the pen hits the map, is a touch of genius.
What a brilliant concept..!!
another Hitler vs. Steiner on youtube: https://www.youtube.com/watch?feature=player_embedded&v=wlCUIW6dU1I
"It can't be solved in polynomial time"
Can you email me proof of this? I really want to win $1 million dollars.
Please note that you was not the first who observed that this statement is not justified -- in the movie we see that Hitler was the first one 🙂
Haha the whole time I was confused. At the beginning they just wanted to connect all the strategic cities with the minimum amount of road, so why no MST from the beginning?
If one wants to connect only subset of points in the metric, then MST is only 2-approximation. Whereas Arora'a algorithm can in principle give almost optimal solutions.
Note that when connecting the *strategic* cities you can also use all the other cities -- this is the Steiner Tree problem. If you were allowed to build roads only between the strategic cities then this would be the Minimum Spanning Tree problem indeed.
niceeeeeeeeeeeeeeeee <3 it
Nice movie 🙂
Oh so very clever! I enjoyed it and will share with friends (those who would enjoy NP-hard humor)!