@inbook{adcc20b2fd3f4f6bb4f889ef8ae2467d,

title = "Relaxations of combinatorial problems via association schemes",

abstract = "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.",

author = "{de Klerk}, E. and {De Oliveira Filho}, F.M. and D.V. Pasechnik",

note = "Pagination: 957",

year = "2012",

language = "English",

isbn = "9781461407683",

series = "International Series in Operations Research & Management Science",

publisher = "Springer Verlag",

number = "166",

pages = "171--200",

editor = "M.F. Anjos and J.B. Lasserre",

booktitle = "Handbook on Semidefinite, Conic and Polynomial Optimization",

address = "Germany",

}