Relaxations of Combinatorial Problems Via Association Schemes

Etienne Klerk (), Fernando M. Oliveira Filho () and Dmitrii V. Pasechnik ()
Additional contact information
Etienne Klerk: Tilburg University
Fernando M. Oliveira Filho: Tilburg University
Dmitrii V. Pasechnik: Nanyang Technological University

Chapter Chapter 7 in Handbook on Semidefinite, Conic and Polynomial Optimization, 2012, pp 171-199 from Springer

Abstract: 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.

Keywords: Adjacency Matrix; Linear Matrix Inequality; Travel Salesman Problem; Regular Graph; Positive Semidefinite (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (3)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-1-4614-0769-0_7

Ordering information: This item can be ordered from
http://www.springer.com/9781461407690

DOI: 10.1007/978-1-4614-0769-0_7

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().