clique

Robust convex relaxation for the planted clique and densest k-subgraph problems

  • Brendan Ames
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    We consider the problem of identifying the densest k-node subgraph in a given graph. We write this problem as an instance of rank-constrained cardinality minimization and then relax using the nuclear and l1 norms. Although the original combinatorial problem is NP-hard, we show that the densest k-subgraph can be recovered from the solution of our … Read more

    Nuclear norm minimization for the planted clique and biclique problems

  • Brendan Ames
  • Stephen A. Vavasis
    • Categories Combinatorial Optimization, Convex Optimization Tags , , , , ,

    We consider the problems of finding a maximum clique in a graph and finding a maximum-edge biclique in a bipartite graph. Both problems are NP-hard. We write both problems as matrix-rank minimization and then relax them using the nuclear norm. This technique, which may be regarded as a generalization of compressive sensing, has recently been … Read more