Polyhedral and Semidefinite Programming Methods in Combinatorial OptimizationShare this page
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
Graduate students and research mathematicians interested in semidefinite programming, combinatorial optimization, lift-and-project methods, convex relaxation methods.