Towards Efficient Higher-Order Semidefinite Relaxations for Max-Cut

Add to your list(s) Download to your calendar using vCal

• Anjos, MF (cole Polytechnique de Montral)
• Wednesday 17 July 2013, 14:30-15:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Polynomial Optimisation

The basic semidefinite relaxation for max-cut underlying the Goemans-Williamson hyperplane rounding procedure can be tightened in different ways. A straightforward approach is to add facet-defining inequalities for the metric polytope, or more generally valid inequalities for the convex hull of incidence vectors of cuts, known as the cut polytope. Other approaches are hierarchical and build a sequence of relaxations that increasingly better approximate the cut polytope but at an increasingly greater computational cost. A natural systematic hierarchy was introduced by Lasserre. The first step in this hierarchy corresponds to the basic semidefinite relaxation which optimizes over the set of correlation matrices. The second step is a relaxation with a matrix of order $n^{2$, and so on.}

We start with the basic semidefinite relaxation intersected with the metric polytope, and propose to iteratively refine this relaxation using semidefiniteness and/or linear constraints derived from selected submatrices of the Lasserre matrix of order $n2$. We present theoretical insights as well as computational results.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.