Finding Dense Subgraphs with Semidefinite Programming

Srivastav, Anand and Wolf, Katja (1998) Finding Dense Subgraphs with Semidefinite Programming.
Published In: Approximation algorithms for combinatorial optimization : proceedings / International Workshop APPROX '98, Aalborg, Denmark, July 18 - 19, 1998, Lecture notes in computer science. 1444 Springer 1998, pp. 181-191.


In this paper 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 Õ(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 arbitrary graphs and k = n/c for c > 1 based on semidefinite programming and randomized rounding which achieves for some c the presently best (randomized) approximation factors.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-301
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 16:25