writeup.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{enumerate}

\begin{document}

\title{Programming Project Writeup}
\author{Kay Toma, Laura Harker, Anna Pham, Jennifer Yu}

\maketitle

\begin{enumerate}
\item FindUsOnTinder
\item cs170-jp
\item Kay Toma, Laura Harker, Anna Pham, Jennifer Yu
\item We used local search looking at swaps of 2 or 4 edges that improved the distance. We generate a psuedo-random path and improve our solution from there. We also looked for valid paths in terms of coloring pattern RB, RRBB, and RRRBBB using the nearest neighbor algorithm, and compared them to our local search results in case they found a better route.
\item Our general approach was following a paper we found online. We first created a Hamiltonian path in the form of a diamond circuit. The diamond circuit could have two paths--north to south and east to west. We could either choose east-west or north-south as the ``true'' path and we hoped to trick algorithms into traveling the north-south path because it was sometimes inexpensive but overall very costly. If anybody tried to run a greedy algorithm, for example, to solve the graph, they would end up with an inaccurately high answer. 
\item We use paths.py as a library. The bulk of the work can be run on 23opt.py. Running ``python 23opt.py'' on the command line will solve all 495 instances. 
\item We used the 1978 paper titled ``Some Examples of Difficult Traveling Salesman Problems'' by Papadimitriou and Steiglitz. 
\end{enumerate}
\end{document}