Combinatorial Optimization Reading Group - Kanstantsin Pashkovich

Title: Quasi-popular Matchings, Optimality, and Extended Formulations

Abstract:

The goal of this talk is to obtain efficient algorithms for computing desirable matchings (wrt cost) by paying the price of mildly relaxing popularity. The main positive result in the talk is a bi-criteria algorithm that finds in polynomial time a "quasi-popular" matching of cost at most opt, where opt is the cost of a min-cost popular matching. Key to the algorithm are a number of results for certain polytopes related to matchings and that we believe to be of independent interest. In particular, we present a polynomial-size extended formulation for an integral polytope sandwiched between the popular and "quasi-popular" matching polytopes. 

Based on paper "Quasi-popular Matchings, Optimality, and Extended Formulations” by Yuri Faenza and Telikepalli Kavitha.