Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Speaker: | Dan McQuillan |
---|---|
Affiliation: | Norwich University |
Room: | Mathematics & Computer Building (MC) 5158 |
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.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.