### Abstract

Original language | English |
---|---|

Title of host publication | Handbook on Semidefinite, Conic and Polynomial Optimization |

Editors | M.F. Anjos, J.B. Lasserre |

Place of Publication | Berlin |

Publisher | Springer Verlag |

Pages | 171-200 |

Number of pages | 957 |

ISBN (Print) | 9781461407683 |

Publication status | Published - 2012 |

### Publication series

Name | International Series in Operations Research & Management Science |
---|---|

Number | 166 |

### Fingerprint

### Cite this

*Handbook on Semidefinite, Conic and Polynomial Optimization*(pp. 171-200). (International Series in Operations Research & Management Science; No. 166). Berlin: Springer Verlag.

}

*Handbook on Semidefinite, Conic and Polynomial Optimization.*International Series in Operations Research & Management Science, no. 166, Springer Verlag, Berlin, pp. 171-200.

**Relaxations of combinatorial problems via association schemes.** / de Klerk, E.; De Oliveira Filho, F.M.; Pasechnik, D.V.

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Scientific › peer-review

TY - CHAP

T1 - Relaxations of combinatorial problems via association schemes

AU - de Klerk, E.

AU - De Oliveira Filho, F.M.

AU - Pasechnik, D.V.

N1 - Pagination: 957

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Chapter

SN - 9781461407683

T3 - International Series in Operations Research & Management Science

SP - 171

EP - 200

BT - Handbook on Semidefinite, Conic and Polynomial Optimization

A2 - Anjos, M.F.

A2 - Lasserre, J.B.

PB - Springer Verlag

CY - Berlin

ER -