Approximation Algorithms and Semidefinite Programming

• Κύριοι συγγραφείς: Gärtner, Bernd (Συγγραφέας), Matousek, Jiri (Συγγραφέας)
• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg, 2012.
• Θέματα: Mathematics.; Computers.; Algorithms.; Computer science > Mathematics.; Applied mathematics.; Engineering mathematics.; Mathematical optimization.; Applications of Mathematics.; Theory of Computation.; Algorithm Analysis and Problem Complexity.; Discrete Mathematics in Computer Science.; Optimization.

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

Πίνακας περιεχομένων:

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