Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization
Seiten
2016
American Mathematical Society (Verlag)
978-1-4704-2811-2 (ISBN)
American Mathematical Society (Verlag)
978-1-4704-2811-2 (ISBN)
- Titel z.Zt. nicht lieferbar
- Versandkostenfrei
- Auch auf Rechnung
- Artikel merken
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 this area.
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.
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.
Levent Tuncel, University of Waterloo, ON, Canada.
Introduction
Duality theory
Ellipsoid method
Primal-dual interior-point methods
Approximation algorithms based on SDP
Geometric representations of graphs
Lift-and-project procedures for combinatorial optimization problems
Lift-and-project ranks for combinatorial optimzation
Successive convex relaxation methods
Connections to other areas of mathematics
An application to discrepancy theory
SDP representability
Bibliography
Index
| Erscheinungsdatum | 03.02.2017 |
|---|---|
| Reihe/Serie | Fields Institute Monographs |
| Verlagsort | Providence |
| Sprache | englisch |
| Maße | 152 x 229 mm |
| Gewicht | 525 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Angewandte Mathematik |
| ISBN-10 | 1-4704-2811-3 / 1470428113 |
| ISBN-13 | 978-1-4704-2811-2 / 9781470428112 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Buch | Softcover (2025)
Springer Vieweg (Verlag)
CHF 62,95
Buch | Softcover (2025)
Springer Fachmedien Wiesbaden (Verlag)
CHF 69,95
Buch | Softcover (2024)
Springer Vieweg (Verlag)
CHF 53,15
