
\subsection{Question:}

\hspace*{1em}You are given a logical array of ($1,000 \times 18,000,000$)

The rows are flight legs

The columns are binary vectors

There are between 2 and 16 1's in each column (very sparse matrix)

Each column has a cost -- and represents a flight that covers the legs
notated by a 1.

The object is to find a subset of the columns
	\begin{itemize}
	\item all flight legs are covered (exactly once)
	\item if there exists more than one solution, find the one of
	minimum cost.
	\end{itemize}

The data is stored in the following format, with 1 row for each column
in the logical table
	\begin{itemize}
	\item The cost of that column,
	\item The number of rows this column covers,
	\item The indices of those rows.
	\end{itemize}

\newpage

\subsection{Answer:}
\subsubsection{Overview:}
\hspace*{1em} Due to the fact that exact-cover is a known {\it
NP-Complete} problem we have a few basic options.  

	\begin{itemize}
	\item First we could use a polynomial number of processors (in
	parallel) and calculate the exact answer which would take and
	exponential amount of time. {\bf Problem:} This would take too
	long.
	\item Secondly we could use an exponential number of processors
	and calculate it in a polynomial amount of time. {\bf Problem:}
	There is no realistic machine that you can do this on for this
	size of problem.
	\item Finally you could come up with some sort of heuristic (or
	a few of them) and evaluate their goodness. This appears to be
	the most reasonable approach.
	\end{itemize}

Therefore, for this problem I am going to describe some heuristic
approaches that may be applicable, and try to characterize their
strengths and weaknesses.

\subsubsection{Heuristics:}

	\paragraph{Genetic Algorithms:}  
	Since this has been the focus of Alice's approach resulting in
	a publication under construction, I will not attempt to cover
	this heuristic.

	\paragraph{Greedy Parallel:}
	Given a machine with say 8,000 processors (MASPAR SIMD class
	machine, (or CM5 class machine with 1,000 processors)) you
	could approach this in a greedy way.  Have each processor take
	$\frac{1}{8,000}$ of the input data (in this case approximately
	$0.1125Meg$ each) and sort those elements based on say average
	cost per city.  Then in parallel all $8,000$ nodes could sort
	the best answer from each node in at worst case $log(8000)$
	parallel time.  (Most Superscalar SIMD machines have a min
	function over all the nodes on a given variable, and has that
	value known to all nodes)

	The greedy approach would add that element to the set, then
	pass that element to all vertices and allow them to maintain a
	vector of all rows that had been covered so far, and use that
	as a mask when sending up it's best map to be sorted globally
	in the next round.  This would continue at most $500$ rounds
	(each column has at least two rows covered)

		\subparagraph{Data Structures:}
		\begin{itemize}
		\item A bit string (number of rows in length) for each
		cpu which will allow each node to keep track of what
		rows have been covered.  
		\item An array to hold the data. and the cost of each
		data element
		\end{itemize}

		\subparagraph{Algorithm:}
		\begin{itemize}
		\item Load the data for this node (locations 1..k)
		\item Initialize variable - $k=1$, $bitmap=0$
		\item Sort the data
		\item Place Min into location Y
		\item Globally find the min value over all Y's
		\item Pass the minimum to all nodes.
		\item Loop till done (no more to check or all covered)
			\begin{itemize}
			\item Mark off those bits as taken in the local
			bit map.
			\item starting at k, check each answer to find
			first one that does not have a row that is
			already covered.
			\item Place the value at k into location Y
			\item Globally find the min value over all Y's
			\item Pass the minimum to all nodes.
			\end{itemize}
		\end{itemize}

		\subparagraph{Analysis:} This heuristic has a few
		strong points going for it.  First it is rapidly
		implementable on a real life machine.  Secondly it will
		probably be very fast on said machine.  Yet, being a
		greedy heuristic, it may select certain members for the
		solution which are sub-optimal.

	\paragraph{Next Heuristic:}
		?????
