In this chapter we describe a novel way of deriving semidefinite programming relaxations of a wide class of combinatorial optimization problems. Many combinatorial optimization problems may be viewed as finding an induced subgraph of a specific type of maximum weight in a given weighted graph. The relaxations we describe are motivated by concepts from algebraic combinatorics. In particular, we consider a matrix algebra that contains the adjacency matrix of the required subgraph, and formulate a convex relaxation of this algebra. Depending on the type of subgraph, this algebra may be the Bose–Mesner algebra of an association scheme, or, more generally, a coherent algebra. Thus we obtain new (and known) relaxations of the traveling salesman problem, maximum equipartition problems in graphs, the maximum stable set problem, etc.
|Title of host publication||Handbook on Semidefinite, Conic and Polynomial Optimization|
|Editors||M.F. Anjos, J.B. Lasserre|
|Place of Publication||Berlin|
|Number of pages||957|
|Publication status||Published - 2012|
|Name||International Series in Operations Research & Management Science|