Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

Details Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

2011-10-06

arxiv.org/abs/1110.1360v1

Computer Science

Data Structures and Algorithms

26 ages, 1 figure. To appear in Symposium on Discrete Algorithms (SODA) 2012

Scientific paper

The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significant gap between known upper and lower bounds for DkS: the current best algorithm gives an ~ O(n^{1/4}) approximation, while even showing a small constant factor hardness requires significantly stronger assumptions than P != NP. In addition to interest in designing better algorithms, a number of recent results have exploited the conjectured hardness of densest k-subgraph and its variants. Thus, understanding the approximability of DkS is an important challenge. In this work, we give evidence for the hardness of approximating DkS within polynomial factors. Specifically, we expose the limitations of strong semidefinite programs from SDP hierarchies in solving densest k-subgraph. Our results include: * A lower bound of Omega(n^{1/4}/log^3 n) on the integrality gap for Omega(log n/log log n) rounds of the Sherali-Adams relaxation for DkS. This also holds for the relaxation obtained from Sherali-Adams with an added SDP constraint. Our gap instances are in fact Erdos-Renyi random graphs. * For every epsilon > 0, a lower bound of n^{2/53-eps} on the integrality gap of n^{Omega(eps)} rounds of the Lasserre SDP relaxation for DkS, and an n^{Omega_eps(1)} gap for n^{1-eps} rounds. Our construction proceeds via a reduction from random instances of a certain Max-CSP over large domains. In the absence of inapproximability results for DkS, our results show that even the most powerful SDPs are unable to beat a factor of n^{Omega(1)}, and in fact even improving the best known n^{1/4} factor is a barrier for current techniques.

Affiliated with

Also associated with

No associations

Rating

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182253