Tutte seminar - Steve VavasisExport this event to calendar

Friday, February 19, 2010 — 3:30 PM to 4:30 PM EST

Convex relaxation for the clique, biclique and clustering problems

Speaker: Dan McQuillan
Affiliation: Norwich University
Room: Mathematics & Computer Building (MC) 5158

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.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)