%From: haglin@theory.cs.mankato.msus.edu (David J. Haglin)
%Subject: Satisfiability
%To: challenge@dimacs.rutgers.edu
%Date: Wed, 13 Jan 93 15:59:27 CST
%-*- Mode:TeX -*-

\documentstyle[twoside,12pt,fleqn]{article}

\textheight = 8.5in
\textwidth = 6.5in
\topmargin = 0pt
\evensidemargin = 1pt
\oddsidemargin = 1pt
\headsep = 10pt
\parskip = 1ex

\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{alg}[theorem]{Algorithm}


\def\QED{\quad\blackslug\lower 8.5pt\null}
\def\Proof{\par\noindent{\sl Proof\/}:\enspace}

\begin{document}

\lineskip 5pt
\lineskiplimit 7pt

\begin{center}
\Huge
Abstract of \\
Comparing MAX-2CNF and \\
MAX-3CNF SAT \\
Algorithms

\vspace{1in}

\large
David J. Haglin \\
Computer and Information Sciences Department \\
Mankato State University \\
Mankato, MN  56002 \\
\vspace{\lineskip}
haglin@epsilon.cs.mankato.msus.edu \\
\end{center}

\vspace{2in}

\section*{Description}

There are three known $3/4$-approximation algorithms for the
MAX 2-CNF Satisfiability problem \cite{Haglin92,Jo74,Ya92}.
These three algorithms will be implemented so that the actual running
time and actual relative error can be compared.
Also, certain characteristics of input instances will be sought
that cause one of the algorithms to perform substantially better
than the others.

\vspace{1in}
\section{Research Objectives}

This research focuses on determining which of the three known
$3/4$-approximation algorithms for the MAX 2-CNF SAT problems
\cite{Haglin92,Jo74,Ya92} performs better on random inputs.
We anticipate that each algorithm will have specific types of inputs
for which it out-performs the others.
We may also discover a way to combine two or three of these algorithms
into either a faster algorithm or one which tends to provide a better
truth assignment.

We will conduct the following research:

\begin{enumerate}
\item Determine how fast each of the algorithms computes its solutions on
       random inputs of various sizes.
\item Determine how often each of the algorithms finds a larger truth
       assignment than the others for random inputs of various sizes.
\item Determine how close to the optimum solution each of the algorithms
       can come on random inputs of various sizes.
       Clearly, this investigation will be limited to smaller input
       sizes.
\item Attempt to identify well-defined characteristics of inputs for
       which each algorithm out-performs the others either in the speed
       or in the relative error.
\item Attempt to identify well-defined characteristics of inputs for
       which each algorithm computes a worst-case (or very poor) truth
       assignment compared to the optimum.
\end{enumerate}

The above work will also be done for MAX 3-CNF SAT.

\section{Approach}

We will implement the algorithms in ANSI C for portability.
We will to make our code available upon completion of this
investigation.
It would help if we could avoid writing a random instance generator
by finding a suitable generator already written in C.

We will begin with smaller instance sizes and gradually increase them,
monitoring our programs to determine how large we can reasonably
expect to get.
If we determine that computing an exact solution is definitely a
hindrance (as we expect), we may look for a good heuristic to help
us find an exact solution more quickly on the average.

We have three workstations on which we can run dedicated processing
for several weeks at a time.
We anticipate that this computing power will be sufficient for us
to carry out our experiments.
We do have other, less dedicated processing facilities that we can
resort to if our workstations do not satisfy our needs.

\section{Support}

We have obtained an internal grant to hire a graduate student
to aid in this research.
The student will write the code and direct the experiments while
looking for trends to formulate conjectures.
It is expected that the graduate student will write a masters
thesis from this work.

\section{Results}

The result of our investigation will be tables comparing running
times and relative error of the three algorithms
on various sizes of inputs.
Such information can be provided immediately
upon running the experiment if this will be useful
to other researchers.
We may be willing to schedule our experimentation based on the
needs of some other research venture.

If we find some characteristic inputs for which one or more of
the algorithms performs exceedingly well or exceedingly poor,
we will certainly describe these characteristics.

We will make our code freely available once the project has reached
completion.

% \bibliographystyle{plain}
% \bibliography{dimacs}

\begin{thebibliography}{1}

\bibitem{Haglin92}
David~J. Haglin.
\newblock Approximating maximum 2-{CNF} satisfiability.
\newblock To appear in Parallel Processing Letters, 1992.

\bibitem{Jo74}
D.S. Johnson.
\newblock Approximation algorithms for combinatorial problems.
\newblock {\em Journal of Computer and System Sciences}, 9:256--278, 1974.

\bibitem{Ya92}
Mihalis Yannakakis.
\newblock On the approximation of maximum satisfiability.
\newblock In {\em Proceedings of the Third {ACM--SIAM} Symposium on Discrete
  Algorithms}, pages 1--9, 1992.

\end{thebibliography}

\end{document}