Unit:
Κατεύθυνση Θεωρητικά ΜαθηματικάLibrary of the School of Science
Supervisors info:
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμ. Μαθηματικών, Ε.Κ.Π.Α.
Αρχοντία Γιαννοπούλου, Επίκουρη Καθηγήτρια, Τμ. Πληροφορικής και Τηλ/νιών, Ε.Κ.Π.Α.
Ιωάννης Μούρτος, Αναπληρωτής Καθηγητής, Τμ. Διοικητικής Επιστήμης και Τεχνολογίας, Ο.Π.Α.
Original Title:
Stable Matchings and Indifference: Structural and Polyhedral Properties
Translated title:
Stable Matchings and Indifference: Structural and Polyhedral Properties
Summary:
Stable Matching is a classical problem of Computer Science. It was defined by Gale in 1962. Since then many generalizations have been studied from different point of views.
One of them is when indifference is allowed.
In this thesis our interest is focused on the classical problem and in the generalisation with indifference.
We study the combinatorial structure of the problems and how is used to produce polyhedral results.
We also research the connection of the polytope of stable matchings with the order polytope of a poset that was defined by Stanley in 1986.
This leads to an alternative method to prove some well-known results about Stable Matching.
Finally we set some open questions for future research.
Main subject category:
Science
Keywords:
Stable Matching, Order Polytope, Indifference, Ties, Rotations
File:
File access is restricted only to the intranet of UoA.
Stable Matchings and Indifference.pdf
534 KB
File access is restricted only to the intranet of UoA.
