\documentstyle[12pt]{article}
\pagestyle{empty}

\hoffset -1.5cm

\textwidth 15cm

\begin{document}

\begin{center}
{\huge RAND-Seminar \\*[1cm]
Freitag, 14. November 1997, 15 Uhr c.t.\\*[1cm]
Seminarraum N327}\\*[1cm]
\end{center}

\begin{center}
{\Large \bf Finding Dense Subgraphs with Semidefinite Programming}

\vspace*{0.5cm}


{\bf \normalsize Katja Wolf \\[.5ex]
        U{\small NIVERSIT\"AT} K{\small \"OLN}}

\end{center}

\vspace*{0.5cm}
\begin{quote}
\baselineskip3ex
\centerline{\bf Abstract}

We consider the problem of computing the heaviest $k$-vertex
induced subgraph of a given graph with nonnegative edge weights. 
This problem is known to be $NP$-hard, but its approximation complexity is not 
known.
For the general problem only an approximation ratio of $\tilde{\O}(n^{0.3885})$
has been proved (Kortsarz and Peleg (1993)). In the last years several authors
analyzed the case $k = \Omega(n)$. In this case Asahiro et al. (1996)
showed a constant factor approximation, and for dense graphs
Arora et al. (1995) obtained even a polynomial-time approximation scheme.
We give a new approximation algorithm for the problem
based on semidefinite programming and randomized rounding which achieves
the presently best (randomized) approximation factors for arbitrary
graphs and $k = n/c$ for $c > 1$.
For example for $k = n/2$ our approximation factor of 0.58 
improves on the previously best approximation factor of 0.44 
due to Asahiro et al.

(Joint work with Anand Srivastav, Humboldt-Universit\"at zu Berlin)

\hspace*{\fill} $\Box$

\end{quote}

\end{document}


