Approximation algorithms and semidefinite programming
Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexit...
Gardado en:
| Auteurs principaux: | , |
|---|---|
| Formato: | Livre numérique |
| Idioma: | Anglais |
| Publicado: |
Berlin, Heidelberg :
Springer Berlin Heidelberg
[20..].
Cham : Springer Nature |
| Edición: | 2012. |
| Acceso en liña: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Nota: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Approximation algorithms and semidefinite programming, Bernd Gärtner, Jiří Matoušek, 2012, Heidelberg, Springer, 1 vol.(XI-251 p.), 978-3-642-22014-2 |
Table des matières:
- Part I (by Bernd Gärtner): 1 Introduction: MAXCUT via Semidefinite Programming 2 Semidefinite Programming 3 Shannon Capacity and Lovász Theta.- 4 Duality and Cone Programming.- 5 Approximately Solving Semidefinite Programs 6 An Interior-Point Algorithm for Semidefinite Programming 7 Compositive Programming.- Part II (by Jiri Matousek): 8 Lower Bounds for the Goemans Williamson MAXCUT Algorithm 9 Coloring 3-Chromatic Graphs 10 Maximizing a Quadratic Form on a Graph 11 Colorings With Low Discrepancy 12 Constraint Satisfaction Problems, and Relaxing Them Semidefinitely 13 Rounding Via Miniatures Summary References Index