**Fields Institute Monographs**

Volume: 27;
2010;
219 pp;
Hardcover

MSC: Primary 90; 15; 52; 65; 05; 68;
**Print ISBN: 978-0-8218-3352-0
Product Code: FIM/27**

List Price: $81.00

Individual Member Price: $64.80

#### You may also like

#### Supplemental Materials

# Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization

Share this page
*Levent Tunçel*

A co-publication of the AMS and Fields Institute

Since the early 1960s, polyhedral methods have
played a central role in both the theory and practice of combinatorial
optimization. Since the early 1990s, a new technique, semidefinite
programming, has been increasingly applied to some combinatorial
optimization problems. The semidefinite programming problem is the
problem of optimizing a linear function of matrix variables, subject
to finitely many linear inequalities and the positive semidefiniteness
condition on some of the matrix variables. On certain problems, such
as maximum cut, maximum satisfiability, maximum stable set and
geometric representations of graphs, semidefinite programming
techniques yield important new results. This monograph provides the
necessary background to work with semidefinite optimization
techniques, usually by drawing parallels to the development of
polyhedral techniques and with a special focus on combinatorial
optimization, graph theory and lift-and-project methods. It allows the
reader to rigorously develop the necessary knowledge, tools and skills
to work in the area that is at the intersection of combinatorial
optimization and semidefinite optimization.

A solid background in mathematics at the undergraduate level and
some exposure to linear optimization are required. Some familiarity
with computational complexity theory and the analysis of algorithms
would be helpful. Readers with these prerequisites will appreciate the
important open problems and exciting new directions as well as new
connections to other areas in mathematical sciences that the book
provides.

Titles in this series are co-published with The Fields Institute for Research in Mathematical Sciences (Toronto, Ontario, Canada).

#### Table of Contents

# Table of Contents

## Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization

#### Readership

Graduate students and research mathematicians interested in semidefinite programming, combinatorial optimization, lift-and-project methods, convex relaxation methods.