Abstract

Dr. Cristian Dobre (Univ. Groningen, NL):

Symmetry reduction in approximation hierarchies for combinatorial problems.

Abstract:
In this presentation we show how one can exploit the symmetry in a
hierarchy of improving semidefinite programming (SDP) relaxations of
NP-hard combinatorial optimization problems. Each level of the
hierarchy consists of a semidefinite part and a system of linear
equations coming from coefficient identification in equalities between
polynomials. Both parts need nontrivial preprocessing in order to
reduce the dimension of the problem, and we show how the symmetry in
the data of the problem can be used to achieve the reduction.
Numerically we exemplify the advantages of this approach by providing
new upper bounds on crossing number instances, one of the most well
known NP-hard combinatorial optimization problem which involves
symmetric data.