##
Approximation of Dense-$k$-Subgraph

###
Han, Ye and Zhang

We consider the DENSE-$k$-SUBGRAPH problem, i.e., determine a block of
$k$ nodes of a weighted graph (of $n$ nodes) such that the total
edge weight within the subgraph induced by the block is maximized.
we present two approximation algorithms for this problem
which are based on linear programming (LP)
and semidefinite programming (SDP) relaxations, respectively.
Our (LP) relaxation based algorithm matches the previously best known
performance guarantee $\frac{k}{n}$, which was obtained by
Feige and Seltser~\cite{Feige2} using an SDP relaxation.
Our second approximation algorithm is based on a strengthened
SDP relaxation comparing with that of Feige and Seltser~\cite{Feige2} and
Srivastav and Wolf~\cite{Srivastav}, and it achieves the presently best
performance guarantee for a wide range of $k$.
Department of Management Sciences\\
Henry B. Tippie College of Business
The University of Iowa
Iowa City, IA 52242, USA, February, 2000

Contact: yinyu-ye@uiowa.edu