Adapting stable matchings to forced and forbidden pairs
References
[1]
S. Bhattacharya, M. Hoefer, C. Huang, T. Kavitha, L. Wagner, Maintaining near-popular matchings, in: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP '15), Springer, 2015, pp. 504–515.
[2]
N. Boehmer, K. Heeger, R. Niedermeier, Deepening the (parameterized) complexity analysis of incremental stable matching problems, in: Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS '22), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 21:1–21:15.
[3]
N. Boehmer, K. Heeger, R. Niedermeier, Theory of and experiments on minimally invasive stability preservation in changing two-sided matching markets, in: Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI '22), AAAI Press, 2022, pp. 4851–4858.
[4]
N. Boehmer, R. Niedermeier, Broadening the research agenda for computational social choice: multiple preference profiles and multiple solutions, in: Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '21), ACM, 2021, pp. 1–5.
[5]
R. Bredereck, J. Chen, D. Knop, J. Luo, R. Niedermeier, Adapting stable matchings to evolving preferences, in: Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI '20), AAAI Press, 2020, pp. 1830–1837.
[6]
K. Cechlárová, L. Gourvès, J. Lesca, On the problem of assigning PhD grants, in: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI '19), ijcai.org, 2019, pp. 130–136.
[7]
M. Charikar, C. Chekuri, T. Feder, R. Motwani, Incremental clustering and dynamic information retrieval, SIAM J. Comput. 33 (2004) 1417–1440.
[8]
Á. Cseh, K. Heeger, The stable marriage problem with ties and restricted edges, Discrete Optim. 36 (2020).
[9]
Á. Cseh, D.F. Manlove, Stable marriage and roommates problems with restricted edges: complexity and approximability, Discrete Optim. 20 (2016) 62–89.
[10]
V.M.F. Dias, G.D. da Fonseca, C.M.H. de Figueiredo, J.L. Szwarcfiter, The stable marriage problem with restricted pairs, Theor. Comput. Sci. 306 (2003) 391–405.
[11]
R. Duan, S. Pettie, H. Su, Scaling algorithms for weighted matching in general graphs, ACM Trans. Algorithms 14 (2018) 8:1–8:35.
[12]
D. Eisenstat, C. Mathieu, N. Schabanel, Facility location in evolving metrics, in: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP '14), Springer, 2014, pp. 459–470.
[13]
C.A. Farrant, J. Tybura, M. Rafe, N. Ackon, M.C. Schmidt, A. Chantaboury, “A brain to pick, an ear to listen and a push in the right direction” (John C. Crosby), Compass: J. Learn. Teach. 14 (2021).
[14]
T. Feder, A new fixed point approach for stable networks and stable marriages, J. Comput. Syst. Sci. 45 (1992) 233–284.
[15]
T. Feder, Network flow and 2-satisfiability, Algorithmica 11 (1994) 291–319.
[16]
I. Feigenbaum, Y. Kanoria, I. Lo, J. Sethuraman, Dynamic matching in school choice: efficient seat reallocation after late cancellations, Manag. Sci. 66 (2020) 5341–5361.
[17]
T. Fleiner, R.W. Irving, D.F. Manlove, Efficient algorithms for generalized stable marriage and roommates problems, Theor. Comput. Sci. 381 (2007) 162–176.
[18]
K. Gajulapalli, J.A. Liu, T. Mai, V.V. Vazirani, Stability-preserving, time-efficient mechanisms for school choice in two rounds, in: Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '20), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 21:1–21:15.
[19]
D. Gale, L.S. Shapley, College admissions and the stability of marriage, Am. Math. Mon. 69 (1962) 9–15.
[20]
S. Gupta, P. Jain, S. Roy, S. Saurabh, M. Zehavi, On the (parameterized) complexity of almost stable marriage, in: Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '20), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 24:1–24:17.
[21]
D. Gusfield, The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments, SIAM J. Comput. 17 (1988) 742–769.
[22]
D. Gusfield, R.W. Irving, The Stable Marriage Problem – Structure and Algorithms. Foundations of Computing Series, MIT Press, 1989.
[23]
G. Haeringer, V. Iehlé, Gradual college admission, J. Econ. Theory 198 (2021).
[24]
K. Hanauer, M. Henzinger, C. Schulz, Recent advances in fully dynamic graph algorithms (invited talk), in: Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND '22), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 1:1–1:47.
[25]
R.W. Irving, An efficient algorithm for the “stable roommates” problem, J. Algorithms 6 (1985) 577–595.
[26]
R.M. Karp, Reducibility among combinatorial problems, in: Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, Plenum Press, New York, 1972, pp. 85–103.
[27]
D.E. Knuth, Mariages stables et leurs relations avec d'autres problèmes combinatoires, Les Presses de l'Université de Montréal, Montreal, Que, 1976, Introduction à l'analyse mathématique des algorithmes, Collection de la Chaire Aisenstadt.
[28]
A. Kunysz, The strongly stable roommates problem, in: Proceedings of the 24th Annual European Symposium on Algorithms (ESA '16), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, pp. 60:1–60:15.
[29]
A. Kunysz, An algorithm for the maximum weight strongly stable matching problem, in: Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC '18), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 42:1–42:13.
[30]
A. Kunysz, K.E. Paluch, P. Ghosal, Characterisation of strongly stable matchings, in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), SIAM, 2016, pp. 107–119.
[31]
D.F. Manlove, Stable marriage with ties and unacceptable partners, Technical Report University of Glasgow, Department of Computing Science, 1999.
[32]
D.F. Manlove, The structure of stable marriage with indifference, Discrete Appl. Math. 122 (2002) 167–181.
[33]
D.F. Manlove, Algorithmics of Matching Under Preferences, Series on Theoretical Computer Science, vol. 2, WorldScientific, 2013.
[34]
D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, Y. Morita, Hard variants of stable marriage, Theor. Comput. Sci. 276 (2002) 261–279.
[35]
D. Marx, I. Schlotter, Parameterized complexity and local search approaches for the stable marriage problem with ties, Algorithmica 58 (2010) 170–187.
[36]
A. Roth, On the allocation of residents to rural hospitals: a general property of two-sided matching markets, Econometrica (1986) 425–427.
Index Terms
- Adapting stable matchings to forced and forbidden pairs
Index terms have been assigned to the content through auto-classification.
Recommendations
Adapting Stable Matchings to Forced and Forbidden Pairs
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent SystemsWe introduce the problem of adapting a stable matching to forced and forbidden pairs. Specifically, given a stable matching M1, a set Q of forced pairs, and a set P of forbidden pairs, we want to find a stable matching that includes all pairs from Q, no ...
The stable marriage problem with restricted pairs
A stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. In an instance of the STABLE MARRIAGE problem, each of the n men and n women ...
A New Approach to Stable Matching Problems
It is shown that Stable Matching problems are the same as problems about stable configurations of X-networks. Consequences include easy proofs of old theorems, a new simple algorithm for finding a stable matching, an understanding of the difference ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
The Author(s).
Publisher
Academic Press, Inc.
United States
Publication History
Published: 01 February 2025
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Feb 2025