Συλλογές
Τίτλος 2-sided and multi-sided stable matchings: structures, algorithms, and applications
Δημιουργός Eirinakis, Pavlos
Συντελεστής Athens University of Economics and Business, Department of Management Science and Technology
Miliotis, Panagiotis
Τύπος Text
Φυσική περιγραφή 186p.
Γλώσσα en
Περίληψη This thesis examines the Stable Matching (SM) problem and some of its most important variants, namely the Stable Admissions (SA), the many-to-many Stable Matching (MM), and the Chain Stable Network (CSN) problem. In the context of the SM problem, a time-optimal algorithm is provided that identifies which of the non-stable pairs can be removed from the agents preference lists without altering the set of solutions. To identify them, we utilize rotations and the transitive reduction of the rotation-poset graph. Then, using a directed line-graph to represent the SM problem, namely the marriage graph, we derive a sparse description of the SM polytope. This description is further reduced to obtain the minimal one by identifying the minimal equation system and the facets of the corresponding polytope. Also, the dimension of the SM polytope is proved to be equal to the number of rotations, while its diameter is also established. Moreover, we study the alternative rotation-based representation of the SM polytope, establishing its dimension and providing its minimal description.Further, we de.ne rotations in the SA setting and propose a time-optimal algorithm for identifying all rotations and all non-stable pairs. This algorithm is then extended to the MM case under pairwise stability, preferences over individuals, and the max-min criterion. In order to maintain the algorithms optimal complexity, we propose the use of a double-stack, a structure which enables exposing and eliminating rotations efficiently. Next, we revisit the corresponding rotation-poset graph and illustrate a time-and space-optimal algorithm for enumerating all solutions to the MM problem. Then, a polynomial algorithm for finding the minimum-weight stable matching is provided, which can also be used to improve the known time-bounds for identifying the egalitarian and the optimal one. The above mentioned algorithms are shown to be applicable even in the case of more complex preference and stability conditions. In a Constraint Programming (CP) context, we show that identifying all stable pairs in the SA and the MM case is equivalent to establishing hyperarc consistency. Furthermore, we provide a predicate which models the MM problem and its encoding as a Constraint Satisfaction Problem. We also propose establishing hyperarc consistency as a preprocessing step in a CP platform, thus obtaining an efficient programming tool to be used especially in the case where specialized algorithms are not applicable (i.e.,in cases where side-constraints are encompassed). The efficiency of our approach is then highlighted by a series of computational results. Last, a multi-sided stable matching configuration is examined; the participating agents are considered to be part of a specialized one-to-one Supply Chain Network (SCN). Under our specialized setting, we prove that every such k-sided SCN can be decomposed into k-1 independent SM sub-markets. Moreover, extending known results on the CSN problem, we show that the set of chain stable networks forms a distributive lattice with respect to the meet and join operations, while intermediary- optimal solutions always exist. Furthermore, we define the notion of contract-rotations, i.e., an extension of rotations, and illustrate that a series of algorithms proposed for the SM problem can be easily extended in our specialized setting.
Λέξη κλειδί Chain Stable Network (CSN) problem
Algorithms
Stable Marriage (SM) problem
Stable Admissions (SA) problem
Many-to-many Stable Matching (MM) problem
Ημερομηνία 10-2010
Άδεια χρήσης https://creativecommons.org/licenses/by/4.0/