
\begin{itemize}
	\item Question: For the Steiner Minimal Tree problem discuss
	three approximation algorithms (of your choice) and compare
	their goodness.

	\item Answer
		\begin{itemize}
		\item Simulated Annealing --
			\begin{enumerate}
			\item randomly generate a tree structure for the
			fixed points.
			\item find length of tree (F.K. Hwang's Linear
			time algorithm for placement of S.P.'s and
			distance Calculation).
			\item Enter Annealer
				\begin{enumerate}
				\item randomly select 2 verticies in the
				tree (such that one is not the parent of
				the other)
				\item randomly re-assign the 4 children
				under them.
				\item Calculate the length of the tree 
				(as above)
				\item if distance is shorter accept, if
				not, accept with a changing probability
				(based on the number of iterations)
				\end{enumerate}
			\item Output Answer
			\end{enumerate}

			Strengths: Simple to implement, easy to run, and
			good parameters seem to carry over from one
			problem to another (contrary to GA's
			
			Weakness: will not change the number of steiner
			points (As designed) therefore it will only try
			to zero in on the shortest ST with as many
			steiner points as were put into the tree to
			start with.

		\item Soap Films -- Pegs for points and they are
			immersed in a liquid soap solution which
			creates a film between the points and adjusts
			connections (steiner points) between them.

			Strength: these generate an answer very quickly
			since they reach a stable point rapidly.

			Weakness: If I remember correctly this method
			has a tendency to give fewer Steiner Points
			than the optimal solution has

		\item Genetic Algorithms -- I haven't come up with a
			good recombination algorithm yet... will try to
			get back to this if I have time.

			Strengths: Currently these are much easier to 
			Parallelize than others on this list.

			Weakness: Parameters need to be tweaked much
			more for each different problem (and even
			problem size) than other Approximation
			Algorithms on this list do.

		\item Neural Nets -- saved for Bonus question.

		\item Minimal Spanning Tree -- obviously must be
			considered as a worst case heuristic since it
			can be calculated in a polynomial time.  This
			distance has been shown to be within a fixed
			distance of the SMT.

		\item MST adaptation -- Starting with a minimal
			Spanning tree, select a vertex at random, then
			select one of it's siblings at random, and
			connect the two and their parent with a steiner
			point set -- if shorter keep, else ignore.

			Strengths: Simple to implement.

			Weakness: If it guesses wrong somewhere, it can
			get in a hole (distance wise) that it can't get
			out of.  

		\end{itemize} 
	\end{itemize}
