Relaxations of Combinatorial Problems Via Association Schemes
Relaxations of Combinatorial Problems Via Association Schemes
复制标题
DOI：
10.1007/978-1-4614-0769-0_7
复制
发表时间：
2012-01-01
期刊：
影响因子：
--
通讯作者：
Pasechnik, Dmitrii V.
中科院分区：
文献类型：
--
作者：
de Klerk, Etienne;de Oliveira Filho, Fernando M.;Pasechnik, Dmitrii V.
在本章中，我们描述了一种推导多种组合优化问题的半定规划松弛的新方法。许多组合优化问题可以看作是在给定的加权图中寻找具有特定类型的最大权的导出子图。我们所描述的松弛是由代数组合学的概念所激发的。特别地，我们考虑了一个矩阵代数，它包含所需的子图的邻接矩阵，并制定了这个代数的凸松弛。根据子图的类型，这个代数可能是一个结合图式的玻色-梅斯纳代数，或者更一般地说，是一个凝聚代数。因此，我们得到新的（和已知的）松弛的旅行商问题，最大均分问题的图，最大稳定集问题等。
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.