Database Matching Service for Stable Marriage Problem

This study revolves around delving into the realm of dynamic preferences within the context of the Stable Marriage Problem (SMP). While the Gale-Shapley algorithm necessitates a time complexity of $O(n^{2})$ to solve an SMP with static preferences, the pursuit of identifying stable matchings under dynamic preferences becomes significantly more time-intensive, entailing a time complexity of $O(k\cdot n!\cdot n^{2})$. The majority of the process involved in discovering stable matchings under dynamic preferences revolves around iterative searching. This circumstance motivates us to develop a database comprising SMP instances and their corresponding stable matchings. This database facilitates a reduction in the time required to uncover static stable matchings from $O(n^{2})$ to $O(n)$. Additionally, our application incorporates several features that enhance users’ comprehension of stable matching structures within SMP instances, including visualization through a lattice structure.