\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\setlength{\parindent}{0em}

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}

\begin{document}

\thispagestyle{empty}
\begin{center}
\textbf{\large
Fall 2013 \qquad Math 566 \qquad Implementation Assignment 5
}
\end{center}

\vspace{1em}
\textbf{\large Problem: Heuristic Methods for TSP}

In this report, you will design heuristic methods to construct ``good'' solutions to the Traveling Salesman Problem where the nodes are points in the Euclidean plane and all distances are the standard Euclidean distance. This assignment is a combination algorithm and visualization assignment: every solution must be presented graphically. You should use some sort of plotting functionality to draw the best tour you can find using your techniques.

You must implement one of each type of algorithm: \textbf{Initial Heuristic} and \textbf{Local Heuristic}. You will produce an initial tour using your initial heuristic and then improve it using your local heuristic. 

\begin{itemize}
\item \textbf{Initial Heuristics}
\begin{itemize}
	\item Nearest Neighbor
	\item Farthest Insertion
	\item Nearest Insertion
	\item Cheapest Insertion
	\item Christofides' Heuristic
\end{itemize}
\item \textbf{Local Heuristics}
\begin{itemize}
	\item 2opt (2-switches)
	\item 3opt (3-switches)
	\item Lin-Kernighan ($\delta$-paths)
\end{itemize}
\end{itemize}

\emph{Special Bonus Assignment:} If you implement an algorithm to produce Held-Karp Lower Bounds, then you will receive up to 10 extra points (out of the 30 total points). If you use such lower bounds, report the vector $\vy = (y_v)_{v\in V}$ and the 1-tree given by the lower bound. Plot the 1-tree and write the vertex values $y_v$ on the nodes. Report the relative difference between your upper and lower bounds.

\vspace{1em}

\textbf{\large Questions to Answer in Your Report}

\textbf{Q1.} Which heuristics did you use?

\textbf{Q2.} How specifically did you select which choices to make?

\textbf{Q3.} What was the most difficult part of this assignment?


\vspace{1em}

\textbf{\large Problem Instances.}

The four problem instances are available online. The files provide lists of points in the integer lattice.



\end{document} 