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 ([ Ссылка ])
Course homepage on CMU's Diderot system: [ Ссылка ]
Thumbnail photo by Rebecca Kiger ([ Ссылка ])
