Combinatorics & Optimization Seminar: Justin Toth

Title: A short new proof that the Stable Matching Polytope is Integral

Abstract:

Vande Vate and Rothblum have written linear programming formulations of weighted stable matching problems on bipartite graphs and proven that the extreme points of the polytopes defining their feasible regions are integral. These results were proven with relatively long and complex extreme point arguments. Recently, as described in the monograph of Lau, Ravi and Singh, the technique of iterative rounding has expanded beyond the domain of approximation algorithms and found its way towards giving new proofs of integrality for classical combinatorial optimization problems. Inspired by this technique we will demonstrate a concise and rather elementary proof that Rothblum's linear description of the stable matching polytope has integral extreme points.