.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