Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

DOI10.1007/s10957-015-0777-xzbMath1327.90189arXiv1305.4891OpenAlexW1572312821MaRDI QIDQ896191

Brendan P. W. Ames

Publication date: 14 December 2015

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.4891

zbMATH Keywords

densest subgraphnuclear norm minimizationplanted clique\(l_1\) norm minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Convex optimization for the densest subgraph and densest submatrix problems ⋮ Exact Clustering of Weighted Graphs via Semidefinite Programming ⋮ On solving the densestk-subgraph problem on large graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Fast alternating linearization methods for minimizing the sum of two convex functions
• Optimal detection of sparse principal components in high dimension
• Guaranteed clustering and biclustering via semidefinite programming
• Nuclear norm minimization for the planted clique and biclique problems
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Expected complexity of graph partitioning problems
• The maximum edge biclique problem is NP-complete
• Hiding cliques for cryptographic security
• Convex optimization for the planted \(k\)-disjoint-clique problem
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Robust principal component analysis?
• Rank-Sparsity Incoherence for Matrix Decomposition
• The highest dimensional stochastic blockmodel with a regularized estimator
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Near-optimal sparse fourier representations via sampling
• Relations between average case complexity and approximation complexity
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Large Cliques Elude the Metropolis Process
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Finding and certifying a large hidden clique in a semirandom graph
• Reducibility among Combinatorial Problems
• Finding Approximately Rank-One Submatrices with the Nuclear Norm and $\ell_1$-Norm
• Finding Hidden Cliques in Linear Time with High Probability
• Algorithms and Computation
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Compressed sensing
• The dense \(k\)-subgraph problem

This page was built for publication: Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation