| Περίληψη: | Στη Θεωρία Γραφημάτων ο γάμος εκφράζεται μέσω προβλημάτων ταιριάσματος (matching problems) σε γραφήματα όπου οι ακμές αναπαριστούν συμβατότητα, δηλ., δύο κορυφές που συνδέονται με ακμή μπορούν να ταιριαστούν ή να "παντρευτούν". Ταίριασμα σε δοσμένο γράφημα είναι ένα υπογράφημά του στο οποίο κάθε κορυφή έχει βαθμό 1. Όταν στο ταίριασμα υπάρχουν όλες οι κορυφές του γραφήματος, το ταίριασμα καλείται πλήρες (perfect matching). Στόχος των προβλημάτων ταιριάσματος είναι η δημιουργία μέγιστου πλήθους συμβατών ζευγαριών. Επιπλέον, ένα ταίριασμα καλείται σταθερό (stable) όταν δεν υπάρχουν ζευγάρια που τα μέλη τους να προτιμούν το ένα το άλλο περισσότερο από τους συντρόφους τους στο ταίριασμα.
Στο πλαίσιο της παρούσας διπλωματικής εργασίας θα ασχοληθούμε με ένα ιδιαίτερο πρόβλημα ταιριάσματος: το Πρόβλημα του Σταθερού Γάμου (the Stable Marriage Problem - SMP). Στη βασική εκδοχή του προβλήματος, δίνονται δύο ισομεγέθη σύνολα αγοριών, Β, και κοριτσιών, G. Κάθε μέλος του συνόλου B (αντίστοιχα του G) διατηρεί τη δική του διαταγμένη λίστα προτιμήσεων για κάθε στοιχείο του συνόλου G (αντίστοιχα του B). Οι προτιμήσεις δεν είναι κατ΄ ανάγκη συμμετρικές και δεν μεταβάλλονται. Στόχος του προβλήματος είναι η δημιουργία σταθερού πλήρους ταιριάσματος, δηλ., η πραγματοποίηση σταθερού "γάμου" μεταξύ όλων των συμμετεχόντων.
Το Πρόβλημα του Σταθερού Γάμου έχει μελετηθεί εκτενώς στην βιβλιογραφία, κυρίως λόγω της ευρείας πρακτικής εφαρμογής του σε πολλούς διαφορετικούς τομείς. Επιπλέον, η ανάπτυξη του αλγορίθμου των Gale και Shapley [D. Gale, L. S. Shapley. College Admissions and the Stability of Marriage. American Mathematical Monthly, 69, pp. 9–14, 1962] για την επίλυσή του έφερε σημαντικές αλλαγές, ιδιαίτερα στους κλάδους των Οικονομικών, της Υγείας και της Πληροφορικής. Χαρακτηριστικές εφαρμογές εμπεριέχουν προβλήματα γνωριμιών, προβλήματα ανάθεσης, όπως π.χ., μαθητών σε σχολεία, ειδικευόμενων γιατρών σε νοσοκομεία, καθώς και προβλήματα ανάθεσης πόρων, όπως π.χ., κατανομή φορτίου κίνησης (load balancing) στο Διαδίκτυο και τον Παγκόσμιο Ιστό. Ωστόσο, η πιο αξιοπρόσεκτη, ίσως, εφαρμογή σχετίζεται με τον εντοπισμό κατάλληλων δοτών νεφρών για ασθενείς που χρήζουν μεταμόσχευσης.
Στόχος της παρούσας διπλωματικής εργασίας είναι αφενός η επισκόπηση της βιβλιογραφίας σχετικά με τη γραφοθεωρητική μελέτη και ανάλυση του Προβλήματος του Σταθερού Γάμου και η παρουσίαση σημαντικών υπαρχουσών εφαρμογών, και αφετέρου η ανάπτυξη αλγοριθμικών λύσεων/συστάσεων για το πρόβλημα ανάθεσης προσωπικού σε ομάδες εργασίας, με βάση αντίστοιχες προσεγγίσεις για το Πρόβλημα του Σταθερού Γάμου, και η θεωρητική και πειραματική μελέτη τους.
|
|---|
