\documentclass[11pt]{article}
\usepackage[letterpaper, left=1in, top=1in, bottom=1in, right=1in]{geometry}
\usepackage{verbatim}
\setlength{\parindent}{0in}
\pagestyle{empty}
\begin{document}
\vspace{\fill}
\begin{center}\LARGE
\textsc{Combinatorics}
\par
\textsc{Seminar}
\end{center}
\vspace{\fill}
\begin{center}\LARGE
\textit{Solving Max-Cut Using Semidefinite Programming}
\end{center}
\vspace{\fill}
\begin{center}\Large
Angelika Wiegele\par
Alpen-Adria-Universit\"{a}t Klagenfurt, Austria
\end{center}
\vspace{\fill}
\textbf{Abstract:} In this talk we present a method for finding exact solutions of the Max-Cut problem (MC), an NP-hard combinatorial optimization problem. This method is based on a relaxation of MC using Semidefinite Programming (SDP). We use a branch and bound setting, that applies the basic SDP bound strengthened by the so-called triangle inequalities. This upper bound is computed by a dynamic version of the bundle method to obtain a "nearly optimal" and "nearly feasible" solution.

\

Besides presenting in detail this bounding routine, we also discuss some branching rules. Furthermore, we review other solution approaches and compare the numerical results with our method. We also extend our experiments to unconstrained quadratic 0-1 problems. The experiments show, that our method nearly always outperforms all other approaches. In particular, where Linear Programming based methods fail (i.e. dense graphs) our method performs very well. Exact solutions are obtained in reasonable time for any instance of size up to n=100 vertices, no matter what density. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so.\vspace{\fill}
\begin{center}\Large
Friday, February 1, 2008, 3:00 pm\par
Mathematics and Science Center: W201
\end{center}
\vspace{\fill}
\begin{center}\Large

\end{center}
\vspace{\fill}
\begin{center}\LARGE
\textsc{Mathematics and Computer Science}\par
\textsc{Emory University}
\end{center}
\end{document}