BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Towards Efficient Higher-Order Semidefinite Relaxations for Max-Cu
 t - Anjos\, MF (cole Polytechnique de Montral)
DTSTART:20130717T133000Z
DTEND:20130717T140000Z
UID:TALK46260@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:The basic semidefinite relaxation for max-cut underlying the G
 oemans-Williamson hyperplane rounding procedure can be tightened in differ
 ent ways. A straightforward approach is to add facet-defining inequalities
  for the metric polytope\, or more generally valid inequalities for the co
 nvex hull of incidence vectors of cuts\, known as the cut polytope. Other 
 approaches are hierarchical and build a sequence of relaxations that incre
 asingly better approximate the cut polytope but at an increasingly greater
  computational cost. A natural systematic hierarchy was introduced by Lass
 erre. The first step in this hierarchy corresponds to the basic semidefini
 te relaxation which optimizes over the set of correlation matrices. The se
 cond step is a relaxation with a matrix of order $n^2$\, and so on. \n\nWe
  start with the basic semidefinite relaxation intersected with the metric 
 polytope\, and propose to iteratively refine this relaxation using semidef
 initeness and/or linear constraints derived from selected submatrices of t
 he Lasserre matrix of order $n^2$. We present theoretical insights as well
  as computational results. \n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR