
Preface  Preview Material  Table of Contents  Supplementary Material 
Fields Institute Monographs 2010; 219 pp; hardcover Volume: 27 ISBN10: 0821833529 ISBN13: 9780821833520 List Price: US$77 Member Price: US$61.60 Order Code: FIM/27 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 liftandproject 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 copublished with The Fields Institute for Research in Mathematical Sciences (Toronto, Ontario, Canada). Readership Graduate students and research mathematicians interested in semidefinite programming, combinatorial optimization, liftandproject methods, convex relaxation methods. 


AMS Home 
Comments: webmaster@ams.org © Copyright 2014, American Mathematical Society Privacy Statement 