Stable Matchings and Indifference: Structural and Polyhedral Properties

Postgraduate Thesis uoadl:2893688 188 Read counter

Unit:
Κατεύθυνση Θεωρητικά Μαθηματικά
Library of the School of Science
Deposit date:
2020-01-09
Year:
2020
Author:
Samaris Michail
Supervisors info:
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμ. Μαθηματικών, Ε.Κ.Π.Α.
Αρχοντία Γιαννοπούλου, Επίκουρη Καθηγήτρια, Τμ. Πληροφορικής και Τηλ/νιών, Ε.Κ.Π.Α.
Ιωάννης Μούρτος, Αναπληρωτής Καθηγητής, Τμ. Διοικητικής Επιστήμης και Τεχνολογίας, Ο.Π.Α.
Original Title:
Stable Matchings and Indifference: Structural and Polyhedral Properties
Languages:
English
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
Index:
No
Number of index pages:
0
Contains images:
No
Number of references:
37
Number of pages:
53
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.