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. 181191.
Abstract
In this paper we consider the problem of computing the heaviest kvertex induced subgraph of a given graph with nonnegative edge weights. This problem is known to be NPhard, 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 polynomialtime 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 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader 
Related URLs: 
ZAIK Number:  zpr97301 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  16 Jan 2012 16:25 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/301 