\documentstyle[11pt]{article}
\textwidth=6in
\textheight=9in
\evensidemargin=0.5in
\oddsidemargin=0.5in
\topmargin=-0.375in
\topskip=0pt
\parindent=3em
\baselineskip=24pt

\input{psfig}
\begin{document}

\Huge

%
% Title Page
%

\vspace*{\fill}
\begin{center}
Parallel Computation\\ of \\ Steiner Minimal Trees \\
\quad \\
\quad \\
Frederick C. Harris, Jr.\\
fredh@cs.unr.edu\\
\quad \\
Department of Computer Science\\
University of Nevada\\
Reno, NV  89557
\end{center}
\vspace*{\fill}

\newpage
\noindent
I.  Introduction
        \begin{itemize}
        \item Original Problem

                \vspace{0.25in}
                \begin{itemize}
                \item Given: 3 points, (A,B,C).
                \vspace{0.25in}
                \item Find: Point X that minimizes\\
                 $dist(A, X)+dist(B,X) + dist(C,X)$
                \vspace{0.25in}
                \item Solved independently by Fermat, \\
                Torrichelli, and Cavalieri.
                \end{itemize}

                \begin{figure}[h]
                \vspace*{22pt}
		\centerline{\psfig{figure=fig-melzak.ps,height=3.1in}}
                \caption{\label{fig:melzak}}
                \vspace*{22pt}
                \end{figure}

        \newpage
        \item First Expansion --
                \begin{itemize}
                \item 4 point problem.
                \item Proposed by Gauss
                \item Four Cities and Railroad lines
                \end{itemize}

        \vspace{1in}

        \item Jacob Steiner --
                \begin{itemize}
                \item 19th Century Professor
                \item University of Berlin
                \item 1 point to many
                \item Actually the 2-D center of Mass
                \end{itemize}

        \vspace{1in}

        \item General Form of the Problem
                \begin{itemize}
                \item Paper by K\"{o}ssler and Jarn\'{i}k ('34)
                \item What is Mathematics? ('41)
                \end{itemize}

        \newpage
        \item First Algorithm
                \begin{itemize}
                \item Melzak ('61)
                \vspace{0.35in}
                \item Replace two points with a third.
                \vspace{0.35in}
                \item $T(n)=2*\left( \begin{array}{c}n\\2\end{array}
                        \right)*T(n-1).$
                \vspace{0.35in}
                \item Given $n$ points and $s$ Steiner Points,
                        Sample Space is of size:

                        \vspace{0.35in}

                        $2^{-n}\left(\begin{array}{c}n\\s+2\end{array}\right)
                        \frac{(n-s-2)!}{s!} $
                \end{itemize}
        \end{itemize}

\newpage
\noindent
II. Exact Computation
        \begin{itemize}
        \vspace{0.4in}
        \item GEOSTEINER
                \vspace{0.3in}
                \begin{itemize}
                \item Published in 1985 by Pawel Winter
                \vspace{0.3in}
                \item Split the process into 2 major pieces
                        \begin{itemize}
                        \vspace{0.3in}
                        \item Generation of lists
                                \begin{itemize}
                                \vspace{0.3in}
                                \item Q\_list
                                \vspace{0.3in}
                                \item T\_list
                                \end{itemize}
                                \vspace{0.3in}
                        \item Extraction of answer from T\_list
                        \end{itemize}
                \vspace{0.3in}
                \item This work has been the basis for \\
                        every exact implementation since.
                \end{itemize}

                \begin{figure}
                {\large
                \input{winter.alg}
                }
                \caption{\label{fig:winter.alg} Steps 2-7 -- Winter's Algorithm}
                \end{figure}

                \begin{figure}
                {\large
                \input{seq.alg.rest}
                }
                \caption{\label{fig:main_loop} Main Loop Properly Structured}
                \end{figure}

	\end{itemize}
\newpage
\noindent
II. Parallel Computation
	\begin{itemize}
	\item Parallel Building Blocks

                \begin{itemize}
                \item a\_before\_b()

                \begin{figure}[h]
                {\Large
                \input{a_before_b.c}
                }
                \caption{\label{fig:a_before_b} Function a\_before\_b()}
               \end{figure}

                \newpage
                \item mate()

                \begin{figure}[h]
                {\Large
                \input{mate.c}
                }
                \caption{\label{fig:mate} Function mate()}
                \end{figure}
                \end{itemize}

        \newpage
        \item First Approach
                \vspace{0.2in}
                \begin{itemize}
                \item Start a new slave for each new \\
                member of Q\_list
                \vspace{0.2in}
                \item Fine for small problems $<15$ points
                \vspace{0.2in}
                \item Ground to a halt rapidly for bigger problems.
                \vspace{0.2in}
                \item 100 point problem can have over 1500 members of
                Q\_list
                \vspace{0.2in}
                \item Messages
                        \begin{itemize}
                        \item Out of Data
                        \item New Node
                        \item New Tree
                        \end{itemize}
                \end{itemize}
        \newpage
        \item Current Approach
                \vspace{0.2in}
                \begin{itemize}
                \item Based upon work by Quinn and Deo
                \vspace{0.05in}
                \item Master with a work Queue.
                \vspace{0.2in}
                \item Fixed number of Slaves
                \vspace{0.2in}
                \item Messages
                        \begin{itemize}
                        \item Out of Data
                        \item New Node
                        \item New Tree
                        \item Change Node
                        \end{itemize}
                \end{itemize}
        \end{itemize}

\newpage
	\hspace{1in}

        \begin{figure}[h]
        \centerline{\psfig{figure=tree.1.before.ps,height=6.0in}}
        \caption{\label{fig:t_list}T\_list for a random set of points.}
        \end{figure}

\newpage
	\hspace{1in}

        \begin{figure}[h]
        \centerline{\psfig{figure=tree.1.ps,height=6.0in}}
        \caption{\label{fig:SMT}SMT extracted from T\_list for a random set of points.}
	\end{figure}
 
%\newpage
%\noindent
%III. Extraction
%
%        \begin{itemize}
%        \item Basically just a Branch and Bound over T\_list with Enhancements
%        \item Incompatibility Matrix
%                \begin{itemize}
%                \item Developed by Cockayne and Hewgill
%                \item Entry i,j tells whether tree[i] and tree[j] can
%                appear together in the answer -- greatly speeds up
%                Branch and Bound.
%                \end{itemize}
%        \item Decomposition
%                \begin{itemize}
%                \item Developed by Cockayne and Hewgill
%                \item Break T\_list into Bi-Connected components
%                \end{itemize}
%        \item Forest Management
%                \begin{itemize}
%                \item Developed by Cockayne and Hewgill
%                \item Remove members of T\_list that cannot appear in
%                        the answer.
%                \end{itemize}
%        \end{itemize}
%

\newpage
\noindent
III.  Computation Results

        \vspace{1in}
        \begin{itemize}
        \item Programs and their Results
        \vspace{1in}

        {\LARGE
        \begin{tabular}{|l|l|l|r|}\hline
        Program & Author(s) &  Points \\ \hline
        STEINER & Cockayne \& Schiller &  7 \\
                & Univ of Victoria &  \\ \hline
        STEINER72 & Boyce \& Serry & 10 \\
                & ATT Bell Labs &  \\ \hline
        STEINER73 & Boyce \& Serry & 12 \\
                &  ATT Bell Labs &  \\ \hline
        GEOSTEINER & Winter & 15 \\
                & Univ of Copenhagen &  \\ \hline
        EDSTEINER86 & Cockayne \& Hewgill & 30 \\
                & Univ of Victoria &  \\ \hline
        EDSTEINER89 & Cockayne \& Hewgill & 100 \\
                & Univ of Victoria &  \\ \hline
        PARSTEINER94 & Harris & 100 \\
                & Clemson University &  \\ \hline
        \end{tabular}
        }
        \newpage
        \item T\_list Computation time
                \vfill
                \begin{itemize}
                \item Literature only discusses averages. \\
                EDSTEINER89 209 minutes \\
                PARSTEINER94 $<20$ minutes
                \vfill
                \item New Data \\(Computation time in Seconds)

                \begin{tabular}{|r|r|}\hline
                PARSTEINER94 & EDSTEINER89 \\ \hline
                1216    & 8597 \\ \hline
                1163    &13466  \\ \hline
                1047    &15872  \\ \hline
                1687    &17061  \\ \hline
                874     &13258  \\ \hline
                1033    &15226  \\ \hline
                1164    &12976  \\ \hline
                1109    &16697  \\ \hline
                975     &15354  \\ \hline
                554     &8650   \\ \hline
                \end{tabular}
                \end{itemize}

        \end{itemize}
\newpage
\noindent
IV. Future Work

        \begin{itemize}
        \vspace{1in}
	\item Extraction Process
		\begin{itemize}
		        \item Further Parallelization
       		         \begin{itemize}
       		         \item Incompatibility Matrix Generation
       		         \item Branch and Bound Extraction
       		         \end{itemize}
       		 \vspace{1in}
       		 \item Thresholds
       		         \begin{itemize}
       		         \item Sorting
       		         \item Cycle Breaking
       		         \item Forest Management
       		         \end{itemize}

		\end{itemize}
\newpage
	\item Other Problems
		\begin{itemize}
	        \item 1-reliable Steiner Tree Problem
	        \begin{figure}[h]
       		 \centerline{\psfig{figure=theta1.ps,height=3.0in}}
       		        \caption{Theta Graph}
       		        \label{fig:Theta}
       		 \end{figure}

       		 \vspace{1in}
       		 \item Addition to existing networks
       		 \end{itemize}
	\end{itemize}
\end{document}

