AMS Bookstore LOGO amslogo
Return to List

AMS TextbooksAMS Applications-related Books

Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization
Levent Tunçel, University of Waterloo, ON, Canada
A co-publication of the AMS and Fields Institute.

Fields Institute Monographs
2010; 219 pp; hardcover
Volume: 27
ISBN-10: 0-8218-3352-9
ISBN-13: 978-0-8218-3352-0
List Price: US$77
Member Price: US$61.60
Order Code: FIM/27
[Add Item]
See also:

Lectures on Global Optimization - Panos M Pardalos and Thomas F Coleman

Polyhedral Computation - David Avis, David Bremner and Antoine Deza

Data Mining and Mathematical Programming - Panos M Pardalos and Pierre Hansen

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).


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

Powered by MathJax

  AMS Home | Comments:
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia