Doubly Nonnegative and Semidefinite Relaxations for the Densest k-Subgraph Problem
Open Access
Abstract
The densest k-subgraph (DkS) maximization problem is to find a set of k vertices with maximum total weight of edges in the subgraph induced by this set. This problem is in general NP-hard. In this paper, two relaxation methods for solving the DkS problem are presented. One is doubly nonnegative relaxation, and the other is semidefinite relaxation with tighter relaxation compare with the relaxation of standard semidefinite. The two relaxation problems are equivalent under the suitable conditions. Moreover, the corresponding approximation ratios’ results are given for these relaxation problems. Finally, some numerical examples are tested to show the comparison of these relaxation problems, and the numerical results show that the doubly nonnegative relaxation is more promising than the semidefinite relaxation for solving some DkS problems.Keywords
This publication has 26 references indexed in Scilit:
- Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphsInformation Processing Letters, 2010
- The Equivalence of Semidefinite Relaxation MIMO Detectors for Higher-Order QAMIEEE Journal of Selected Topics in Signal Processing, 2009
- A constant approximation algorithm for the densest k-subgraph problem on chordal graphsInformation Processing Letters, 2008
- A deterministic approximation algorithm for the Densest k-Subgraph ProblemInternational Journal of Operational Research, 2008
- Upper bounds and exact algorithms for -dispersion problemsComputers & Operations Research, 2006
- Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous CDMAIEEE Transactions on Signal Processing, 2002
- The Dense k -Subgraph ProblemAlgorithmica, 2001
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- A recipe for semidefinite relaxation for (0,1)-quadratic programmingJournal of Global Optimization, 1995
- Clustering and domination in perfect graphsDiscrete Applied Mathematics, 1984