Approximation Algorithms and Semidefinite Programming

• Main Authors: Gärtner, Bernd (Author), Matousek, Jiri (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2012.
• Subjects: 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...

Table of Contents:

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