Social Classroom Seating Assignment Problems

University students benefit academically, personally and professionally from an expansion of their in-class social network. To facilitate this, we present a novel and broadly applicable optimization approach that exposes individuals to as many as possible peers that they do not know. This novel class of ‘social seating assignment problems’ is parameterized by the social network, … Read more

On Matroid Parity and Matching Polytopes

The matroid parity (MP) problem is a powerful (and NP-hard) extension of the matching problem. Whereas matching polytopes are well understood, little is known about MP polytopes. We prove that, when the matroid is laminar, the MP polytope is affinely congruent to a perfect b-matching polytope. From this we deduce that, even when the matroid … Read more