Goemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory Toolkit

Item: Goemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory Toolkit
Rating: 5
Author: PostSingularity Institute

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer science UYAMathematical theory of computation

🎙 Ryan O'Donnell 👥 14K 📅 June 15, 2020 ⏱ 31 min 👁 2K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

Max-CutSDPRoundingApproximationGoemans-Williamson

Summary

This lecture, part of the CS Theory Toolkit course at CMU, focuses on the Goemans-Williamson algorithm for approximating the Max-Cut problem. The instructor, Ryan O’Donnell, begins by recapping the Max-Cut problem and its formulation as an integer program. He then introduces the semidefinite programming (SDP) relaxation, explaining how it can be solved in polynomial time and how the solution provides a vector for each vertex. The lecture illustrates the SDP relaxation with the example of a 5-cycle, where the optimal vector solution corresponds to Lovász’s umbrella, achieving an SDP value of approximately 4.5. The core of the lecture is the rounding technique: a random hyperplane is chosen through the origin, and vertices are assigned to sides based on the sign of the dot product with the hyperplane’s normal vector. The analysis shows that the probability an edge is cut is proportional to the angle between the vectors, and this probability is at least 0.878 times the SDP contribution for that edge. Summing over all edges, the expected cut size is at least 0.878 times the SDP optimum, which in turn is at least the true maximum cut. This yields the famous 0.878-approximation guarantee for Max-Cut.

195 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous explanation of the Goemans-Williamson algorithm. The value lies in its pedagogical approach: it builds from the basics of SDP, illustrates with a concrete example, and then carefully derives the approximation guarantee. The argumentation is solid, with each step logically justified. The use of geometric intuition (e.g., Lovász’s umbrella, random hyperplane) enhances understanding. The analysis of the rounding probability is particularly well-presented, showing the relationship between the angle and the cut probability, and the final comparison of the two curves is convincing.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with precise mathematical definitions and derivations. The instructor references the original Goemans-Williamson paper and provides additional resources in the description. The title accurately reflects the content. The lecture is part of a well-structured graduate course, indicating a high level of academic quality. No comments were provided for analysis.

156 words

Title / Content Match

The title accurately describes the lecture's focus on the Goemans-Williamson rounding technique for the Max-Cut SDP.

Quality & Reliability

9/10

Lecture by a recognized expert in theoretical computer science, part of a graduate course at Carnegie Mellon University. The content is mathematically rigorous, with clear derivations and references to the original Goemans-Williamson paper. The presentation is well-structured and the technical details are accurate.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Approximability of CSPs — Slides referenced in the lecture for further reading on CSP approximation.
Ryan O'Donnell's homepage — Instructor's academic homepage.
Course homepage on Diderot — Course materials and information.
Rebecca Kiger photography — Photographer credited for the thumbnail image.

Concurring Sources

Goemans and Williamson (1995) — Original paper presenting the 0.878-approximation algorithm for Max-Cut.
Semidefinite Programming — General reference for SDP, which is the basis of the relaxation.

Contribution & Novelties

The lecture provides a clear and accessible explanation of the Goemans-Williamson algorithm, a landmark result in approximation algorithms. It offers a detailed walkthrough of the SDP relaxation and the random hyperplane rounding technique, making the material accessible to graduate students. The use of the 5-cycle example and Lovász’s umbrella helps illustrate the concepts. The lecture also connects to broader topics in constraint satisfaction problems (CSPs) and their approximability.

Pour aller plus loin :

Semidefinite programming — Background on SDP, which is central to the algorithm.
Max-cut problem — Overview of the problem and its significance.
Goemans-Williamson algorithm — Detailed description of the algorithm and its approximation ratio.
Constraint satisfaction problem — General framework for CSPs, relevant to the lecture’s context.
Lovász umbrella — Related to the geometric construction used in the example.

132 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a lecture that is both information-dense and technically rigorous. The balance between quantity and quality of information is excellent, and the technical level is appropriate for a graduate audience. The high reliability score reflects the expertise of the instructor and the solid mathematical foundations.

Reliability 9/10