Dima Pasechnik (Nanyang Technological University)「Representations of semidefinite program algebras and bounds for
combinatorial optimisation problems」
概要: Linear optimisation over the intersection of the cone of positive
semidefinite matrices with an affine subspace, usually called
semidefinite programming (SDP), provides an important modeling tool in
combinatortial optimisation, optimal control, etc. The matrix data of
the SDP generates a subalgebra of the full matrix algebra,
often it is a coherent configuration, or even an association scheme,
and its representations can be used to solve the SDP more
efficiently---a generalisation of the approach pioneered
by Delsarte's work on bounds for codes. We discuss applications
of this technique to various combinatorial problems, such as lower
bounds for crossing numbers of complete graphs, upper bounds on codes
(e.g. permutation codes), approximation schemes for TSP, etc.
References:
http://www.optimization-online.org/DB_HTML/2010/07/2690.html
http://dx.doi.org/10.1007/s10107-006-0039-7
(or the preprint of latter:
http://www.optimization-online.org/DB_HTML/2005/03/1083.html)