Stable Matching

This term our reading group studies Matching under Preferences. In the words of Egres Open

From the viewpoint of combinatorial optimization, stable matching problems are interesting because there are many beautiful algorithmic and structural results, yet these do not seem to fit into the usual framework of flows and matchings. The field is quite active and generalizations have been achieved in several directions, but a unified understanding of the results is still missing.

The suggested papers are available below the schedule. If you would like to present one of the unclaimed papers, or suggest a paper to present, please get in touch with one of the organizers.

Schedule

Date Topic Presenter
May 10th, 2019 Overview Talk One Time Room Change: MC 5417 Justin Toth
May 17th, 2019 A Fixed-Point Approach to Stable Matchings and Some Applications by Tamas Fleiner. Cedric Koh
May 24th, 2019 No Talks on account of IPCO 2019 IPCO
May 31st, 2019 A Fixed-Point Approach to Stable Matchings and Some Applications by Tamas Fleiner. Independent of previous talk Akshay Ramachandran
Jun 07th, 2019 Popular Matchings by David Abraham, Robert Irving, Telikepalli Kavitha, and Kurt Melhorn Lily Wang
Jun 14th, 2019 Popularity, Mixed Matchings, and Self-Duality by Chien-Chung Huang and Telikepalli Kavitha. Adam Brown
Jun 21st, 2019 Popular Matchings in the Stable Marriage Problem by Chien-Chung Huang and Telikepalli Kavitha. Ishan Bansal
Jun 28th, 2019 Better and Simpler Approximation Algorithms for the Stable Marriage Problem by Zoltan Kiraly. Madison Van Dyk
Jul 05th, 2019 Quasi-Popular Matchings, Optimality, and Extended Formulations by Yuri Faenza and Telikepalli Kavitha. Kanstantsin Pashkovich
Jul 12th, 2019 A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists by Chi-Kit Lam and Gregory Plaxton. Madison Van Dyk
Jul 19th, 2019 On Stable Matchings and Flows by Tamas Fleiner. Sharat Ibrahimpur
Jul 26th, 2019 New and Simple Algorithms for Stable Flow Problems by Agnes Cseh and Jannik Matuschke. Justin Toth
Aug 02nd, 2019 Stable Marriage with General Preferences by Linda Farczadi, Konstantinos Georgiou, and Jochen Koenemann. Matt Gerstbrein

Suggested Papers

  1. Claimed A Fixed-Point Approach to Stable Matchings and Some Applications by Tamas Fleiner.

  2. To be claimed Pairwise Preferences in the Stable Marriage Problem by Agnes Cseh and Attila Juhos.

  3. Claimed Popular Matchings by David Abraham, Robert Irving, Telikepalli Kavitha, and Kurt Melhorn.

  4. Claimed Popularity, Mixed Matchings, and Self-Duality by Chien-Chung Huang and Telikepalli Kavitha.

  5. Claimed Popular Matchings in the Stable Marriage Problem by Chien-Chung Huang and Telikepalli Kavitha.

  6. To be claimed Popular Matchings and Limits to Tractability by Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, and Xingyu Zhang.

  7. Claimed Quasi-Popular Matchings, Optimality, and Extended Formulations by Yuri Faenza and Telikepalli Kavitha.

  8. To be claimed Three-dimensional stable matching with cyclic preferences by Kimo Eriksson, Jonas Sjostrand, and Pontus Strimling.

  9. To be claimed Three-sided stable matchings with cyclic preferences by Peter Biro and Eric McDermid

  10. Claimed Stable Marriage with General Preferences by Linda Farczadi, Konstantinos Georgiou, and Jochen Koenemann.

  11. Claimed Better and Simpler Approximation Algorithms for the Stable Marriage Problem by Zoltan Kiraly.

  12. Claimed On Stable Matchings and Flows by Tamas Fleiner.

13.Claimed New and Simple Algorithms for Stable Flow Problems by Agnes Cseh and Jannik Matuschke.

  1. To be claimed Finding Stable Matchings that are Robust to Errors in the Input by Tung Mai and Vijay Vazirani.

  2. To be claimed Stable Matchings, Robust Solutions, and Distributive Lattices by Tung Mai and Vijay Vazirani.

  3. Claimed A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists

Previous
Next