13 thoughts on “A students homework in algorithms

    • 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 🙂

  1. 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.

Leave a Reply to Ondrej Cancel reply

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