Finding Dense Subgraphs with Semidefinite Programming
Srivastav, Anand and Wolf, Katja
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.
|Item Type:||Proceedings article|
|Citations:||56 (Google Scholar) ||
|Uncontrolled Keywords:||approximation algorithms randomized algorithms semidefinite programming subgraph problem|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader|
|Depositing User:||Archive Admin|
|Date Deposited:||02 Apr 2001 00:00|
|Last Modified:||16 Jan 2012 16:25|