National and Kapodistrian University of Athens
Stable Matchings and Indifference: Structural and Polyhedral Properties
Abstract
dc:descriptionΈνα κλασσικό πρόβλημα στην επιστήμη της Πληροφορικής που ορίστηκε από τον Gale το 1962 είναι το πρόβλημα του ευσταθούς ταιριάσματος. Από τότε πολλές γενικεύσεις του προβλήματος αυτού έχουν μελετηθεί απο διάφορες οπτικές. Μία από αυτές είναι οτι επιτρέπονται συνθήκες αδιαφορίας. Σε αυτή την διπλωματική ασχολούμαστε με την κλασσική εκδοχή του προβλήματος αλλά και την γενίκευση με τις συνθήκες αδιαφορίας. Μελετάμε την συνδυαστική δομή των προβλημάτων και πως αξιοποιούνται για να παράγουν πολυεδρικά αποτελέσματα. Αναδεικνύουμε την σχέση του πολυτόπου των ευσταθών ταιριασμάτων με το πολύτοπο διάταξης ενός μερικώς διατεταγμένου συνόλου που όρισε ο Stanley το 1986. Αυτό μας οδηγεί σε μία εναλλακτική μέθοδο για να αποδείξουμε κάποια γνωστα αποτελέσματα σχετικά με το πρόβλημα. Τέλος θέτουμε και κάποια ανοιχτά ερωτήματα για μελλοντική έρευνα.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Σάμαρης Μιχαήλ
- Samaris Michail
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:2893688