New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education
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.
 SEARCH THIS BOOK:
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

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