Relaxations of combinatorial problems via association schemes

E. de Klerk, F.M. De Oliveira Filho, D.V. Pasechnik

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

12 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationHandbook on Semidefinite, Conic and Polynomial Optimization
EditorsM.F. Anjos, J.B. Lasserre
Place of PublicationBerlin
PublisherSpringer Verlag
Pages171-200
Number of pages957
ISBN (Print)9781461407683
Publication statusPublished - 2012

Publication series

NameInternational Series in Operations Research & Management Science
Number166

Fingerprint Dive into the research topics of 'Relaxations of combinatorial problems via association schemes'. Together they form a unique fingerprint.

Cite this