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

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>