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

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

Association Scheme
Combinatorial Problems
Algebra
Combinatorial Optimization Problem
Subgraph
Semidefinite Programming Relaxation
Convex Relaxation
Equipartition
Stable Set
Matrix Algebra
Adjacency Matrix
Weighted Graph
Induced Subgraph
Travelling salesman problems
Combinatorics
Graph in graph theory

Cite this

de Klerk, E., De Oliveira Filho, F. M., & Pasechnik, D. V. (2012). Relaxations of combinatorial problems via association schemes. In M. F. Anjos, & J. B. Lasserre (Eds.), Handbook on Semidefinite, Conic and Polynomial Optimization (pp. 171-200). (International Series in Operations Research & Management Science; No. 166). Berlin: Springer Verlag.
de Klerk, E. ; De Oliveira Filho, F.M. ; Pasechnik, D.V. / Relaxations of combinatorial problems via association schemes. Handbook on Semidefinite, Conic and Polynomial Optimization. editor / M.F. Anjos ; J.B. Lasserre. Berlin : Springer Verlag, 2012. pp. 171-200 (International Series in Operations Research & Management Science; 166).
@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",

}

de Klerk, E, De Oliveira Filho, FM & Pasechnik, DV 2012, Relaxations of combinatorial problems via association schemes. in MF Anjos & JB Lasserre (eds), 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.

Handbook on Semidefinite, Conic and Polynomial Optimization. ed. / M.F. Anjos; J.B. Lasserre. Berlin : Springer Verlag, 2012. p. 171-200 (International Series in Operations Research & Management Science; No. 166).

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-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 -

de Klerk E, De Oliveira Filho FM, Pasechnik DV. Relaxations of combinatorial problems via association schemes. In Anjos MF, Lasserre JB, editors, Handbook on Semidefinite, Conic and Polynomial Optimization. Berlin: Springer Verlag. 2012. p. 171-200. (International Series in Operations Research & Management Science; 166).