Convex optimization for the densest subgraph and densest submatrix problems

Polina Bombina, Brendan Ames

We consider the densest $k$-subgraph problem, which seeks to identify the $k$-node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP…