##
.519 Approximation of Dense-n/2-Subgraph

###
Yinyu Ye and Jiawei Zhang

We consider the DENSE-n/2-SUBGRAPH problem, i.e., determine a block of
half nodes such that the weight within the subgraph induced by the
block is maximized. We prove that a mixed semidefinite relaxation and
simple randomization technique yield a .519 approximations of
DENSE-n/2-SUBGRAPH. The previous best-known results for this problem
is .5 using a simple randomization technique and .48 using a
semidefinite relaxation, which provably yields no more than .5
approximation.
Working Paper, Department of Management Sciences,
Henry B. Tippie College of Business,
The University of Iowa, Iowa City, Iowa 52242.

Contact: yinyu-ye@uiowa.edu