Relaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory Toolkit @RyanODonnellTeaching
Relaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory Toolkit  @RyanODonnellTeaching
Uploaded June 2020 | Updated November 2026, 1 day ago
The Bipartite Max-Perfect-Matching problem is used as an example of a problem that can be captured exactly by an Integer Linear Program (ILP), and then relaxed to an LP. Luckily, this relaxation still has optimal integral solutions! Lecture 18b of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.

Resources for this lecture:
"Understanding and Using Linear Programming" by Matoušek and Gärtner
"Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász, and Schrijver

Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)

Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/

Thumbnail photo by Rebecca Kiger (rebeccakphoto.com/)
Relaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory ToolkitPauli error estimation via Population RecoveryGoemans Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory ToolkitComputational Indistinguishability || @ CMU || Lecture 25b of CS Theory ToolkitInformation Complexity || @ CMU || Lecture 24c of CS Theory ToolkitA problem re the k-Consistency Algorithm for CSPs  || @ CMU || Recitation 11 of CS Theory ToolkitMax-st-Flow is an LP || @ CMU || Lecture 18a of CS Theory Toolkit#48/100: |v⟩ and −|v⟩ are indistinguishable || Quantum Computer Programming in 100 Easy LessonsAlgorithms for Bounded Treewidth || @ CMU || Lecture 22(c) of CS Theory ToolkitSemidefinite relaxation problems || @ CMU || Recitation 10 of CS Theory ToolkitThe Math Behind Quantum Algorithms (in Scratch!)Quantum Monte Carlo: Mean Estimation when you have the source code
Ryan ODonnell |

Relaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory Toolkit

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER