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
-
Claimed A Fixed-Point Approach to Stable Matchings and Some Applications by Tamas Fleiner.
-
To be claimed Pairwise Preferences in the Stable Marriage Problem by Agnes Cseh and Attila Juhos.
-
Claimed Popular Matchings by David Abraham, Robert Irving, Telikepalli Kavitha, and Kurt Melhorn.
-
Claimed Popularity, Mixed Matchings, and Self-Duality by Chien-Chung Huang and Telikepalli Kavitha.
-
Claimed Popular Matchings in the Stable Marriage Problem by Chien-Chung Huang and Telikepalli Kavitha.
-
To be claimed Popular Matchings and Limits to Tractability by Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, and Xingyu Zhang.
-
Claimed Quasi-Popular Matchings, Optimality, and Extended Formulations by Yuri Faenza and Telikepalli Kavitha.
-
To be claimed Three-dimensional stable matching with cyclic preferences by Kimo Eriksson, Jonas Sjostrand, and Pontus Strimling.
-
To be claimed Three-sided stable matchings with cyclic preferences by Peter Biro and Eric McDermid
-
Claimed Stable Marriage with General Preferences by Linda Farczadi, Konstantinos Georgiou, and Jochen Koenemann.
-
Claimed Better and Simpler Approximation Algorithms for the Stable Marriage Problem by Zoltan Kiraly.
-
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.
-
To be claimed Finding Stable Matchings that are Robust to Errors in the Input by Tung Mai and Vijay Vazirani.
-
To be claimed Stable Matchings, Robust Solutions, and Distributive Lattices by Tung Mai and Vijay Vazirani.