BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Towards Efficient Higher-Order Semidefinite Relaxa
tions for Max-Cut - Anjos\, MF (cole Polytechnique
de Montral)
DTSTART;TZID=Europe/London:20130717T143000
DTEND;TZID=Europe/London:20130717T150000
UID:TALK46260AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/46260
DESCRIPTION:The basic semidefinite relaxation for max-cut unde
rlying the Goemans-Williamson hyperplane rounding
procedure can be tightened in different ways. A st
raightforward approach is to add facet-defining in
equalities for the metric polytope\, or more gener
ally valid inequalities for the convex hull of inc
idence vectors of cuts\, known as the cut polytope
. Other approaches are hierarchical and build a se
quence of relaxations that increasingly better app
roximate the cut polytope but at an increasingly g
reater computational cost. A natural systematic hi
erarchy was introduced by Lasserre. The first step
in this hierarchy corresponds to the basic semide
finite relaxation which optimizes over the set of
correlation matrices. The second step is a relaxat
ion with a matrix of order $n^2$\, and so on. \n\n
We start with the basic semidefinite relaxation in
tersected with the metric polytope\, and propose t
o iteratively refine this relaxation using semidef
initeness and/or linear constraints derived from s
elected submatrices of the Lasserre matrix of orde
r $n^2$. We present theoretical insights as well a
s computational results. \n\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR