An error was encountered while trying to add the item to the cart. Please try again.
The following link can be shared to navigate to this page. You can select the link to copy or click the 'Copy To Clipboard' button below.
Copy To Clipboard
Successfully Copied!
Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization

Levent Tunçel University of Waterloo, Waterloo, ON, Canada
A co-publication of the AMS and Fields Institute
Available Formats:
Softcover ISBN: 978-1-4704-2811-2
Product Code: FIM/27.S
List Price: $86.00 MAA Member Price:$77.40
AMS Member Price: $68.80 Electronic ISBN: 978-1-4704-1790-1 Product Code: FIM/27.E List Price:$81.00
MAA Member Price: $72.90 AMS Member Price:$64.80
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $129.00 MAA Member Price:$116.10
AMS Member Price: $103.20 Click above image for expanded view Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization Levent Tunçel University of Waterloo, Waterloo, ON, Canada A co-publication of the AMS and Fields Institute Available Formats:  Softcover ISBN: 978-1-4704-2811-2 Product Code: FIM/27.S  List Price:$86.00 MAA Member Price: $77.40 AMS Member Price:$68.80
 Electronic ISBN: 978-1-4704-1790-1 Product Code: FIM/27.E
 List Price: $81.00 MAA Member Price:$72.90 AMS Member Price: $64.80 Bundle Print and Electronic Formats and Save! This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.  List Price:$129.00 MAA Member Price: $116.10 AMS Member Price:$103.20
• Book Details

Fields Institute Monographs
Volume: 272010; 219 pp
MSC: Primary 90; 15; 52; 65; 05; 68;

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.

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

• Chapters
• Chapter 1. Introduction
• Chapter 2. Duality theory
• Chapter 3. Ellipsoid method
• Chapter 4. Primal-dual interior-point methods
• Chapter 5. Approximation algorithms based on SDP
• Chapter 6. Geometric representations of graphs
• Chapter 7. Lift-and-project procedures for combinatorial optimization problems
• Chapter 8. Lift-and-project ranks for combinatorial optimzation
• Chapter 9. Successive convex relaxation methods
• Chapter 10. Connections to other areas of mathematics
• Chapter 11. An application to discrepancy theory
• Chapter 12. SDP representability

• Request Review Copy
Volume: 272010; 219 pp
MSC: Primary 90; 15; 52; 65; 05; 68;

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.

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

• Chapters
• Chapter 1. Introduction
• Chapter 2. Duality theory
• Chapter 3. Ellipsoid method
• Chapter 4. Primal-dual interior-point methods
• Chapter 5. Approximation algorithms based on SDP
• Chapter 6. Geometric representations of graphs
• Chapter 7. Lift-and-project procedures for combinatorial optimization problems
• Chapter 8. Lift-and-project ranks for combinatorial optimzation
• Chapter 9. Successive convex relaxation methods
• Chapter 10. Connections to other areas of mathematics
• Chapter 11. An application to discrepancy theory
• Chapter 12. SDP representability
You may be interested in...
Please select which format for which you are requesting permissions.