Tutte seminar - Steve Vavasis

Convex relaxation for the clique, biclique and clustering problems

Abstract:

We consider the clique, biclique, and clustering problems in the case that the problem instance consists of a clique, biclique, or perfectly clustered data plus some noisy data. The noisy data may be inserted either by an adversary or at random. We show that instances constructed in this manner may be solved by convex relaxation even though clique, biclique, and clustering are all NP-hard. In the case of clique and biclique, our convex relaxation uses the nuclear norm, which has recently been proved in a series of papers to exactly solve the NP-hard matrix completion problem for instances that are constructed in a similar manner. 

This talk represents joint work with B. Ames of University of Waterloo.