Convex optimization for the densest subgraph and densest submatrix problems
DOI10.48550/arXiv.1904.03272zbMath1459.90173arXiv1904.03272OpenAlexW3085521625MaRDI QIDQ142862
Polina Bombina, Brendan Ames, Polina Bombina, Brendan P. W. Ames
Publication date: 5 April 2019
Published in: SN Operations Research Forum (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.03272
maximum cliquealternating direction method of multipliersdensest subgraphnuclear norm relaxationsubmatrix localization
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Convex programming (90C25) Combinatorial optimization (90C27)
Related Items (1)
Uses Software
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
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Guaranteed clustering and biclustering via semidefinite programming
- Spectral clustering and the high-dimensional stochastic blockmodel
- User-friendly tail bounds for sums of random matrices
- Nuclear norm minimization for the planted clique and biclique problems
- Community detection in sparse networks via Grothendieck's inequality
- Finding one community in a sparse graph
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Recovery guarantees for exemplar-based clustering
- The maximum clique problem
- Hiding cliques for cryptographic security
- On semidefinite relaxations for the block model
- Consistency of spectral clustering in stochastic block models
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Exact Recovery in the Stochastic Block Model
- Improved Graph Clustering
- Relations between average case complexity and approximation complexity
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Submatrix localization via message passing
- Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
- Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log*|V|) time
- Graph Partitioning and Graph Clustering
- Reducibility among Combinatorial Problems
- Information Limits for Recovering a Hidden Community
- Finding Hidden Cliques in Linear Time with High Probability
- An Introduction to Matrix Concentration Inequalities
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
This page was built for publication: Convex optimization for the densest subgraph and densest submatrix problems
