2-μερή και πολύ-μερή Ευσταθή Ταιριάσματα: Δομές, αλγόριθμοι και εφαρμογές

  • -

2-μερή και πολύ-μερή Ευσταθή Ταιριάσματα: Δομές, αλγόριθμοι και εφαρμογές

Category : PhD ADOPT , PhD Completed , PhDs

Περιγραφή Διδακτορικής Διατριβής

Η διδακτορική διατριβή του Δρ. Παύλου Ειρηνάκη έχει τίτλο “2-μερή και πολύ-μερή Ευσταθή Ταιριάσματα: Δομές, αλγόριθμοι και εφαρμογές”. Η κύρια συνεισφορά της διατριβής του συνίσταται στα ακόλουθα: (1) Τη δημιουργία ενός αλγορίθμου βέλτιστης πολυπλοκότητας για την αναγνώριση όλων των μη-ευσταθών ζευγαριών που δεν μπορούν να αφαιρεθούν από τις λίστες προτίμησης χωρίς να επηρεάσουν το σύνολο των λύσεων ενός προβλήματος Ευσταθούς Γάμου (ΕΓ). (2) Τον καθορισμό διαφόρων θεμελιακών χαρακτηριστικών του πολυτόπου ΕΓ, όπως η διάστασή του, η διάμετρος καθώς και η ελάχιστη περιγραφή του, δηλαδή το ελάχιστο σύστημα ισοτήτων και το συνόλου των προσόψεών του. (3) Τον καθορισμό της διάστασης και της ελάχιστης περιγραφής του βασιζόμενου στις περιστροφές πολυτόπου ΕΓ. (4) Τη δημιουργία αλγορίθμων βέλτιστης πολυπλοκότητας για την εύρεση του συνόλου των μη-ευσταθών ζευγαριών για το πρόβλημα της Ευσταθούς Αποδοχής (ΕΑ) καθώς και για το πρόβλημα του πολλά-προς-πολλά Ευσταθούς Ταιριάσματος (ΕΤ). (5) Τη δημιουργία ενός χρονικά και χωρικά βέλτιστου αλγορίθμου για την εύρεση του συνόλου των λύσεων για το πρόβλημα ΕΤ καθώς και ενός αλγορίθμου βέλτιστης πολυπλοκότητας για την εύρεση της λύσης ελάχιστης “μετάνοιας” (minimum regret). (6) Την δημιουργία ενός πολυωνυμικού αλγορίθμου για την εύρεση της λύσης ελαχίστου “βάρους” (minimum weight) για το πρόβλημα ΕΤ, ο οποίος βελτιώνει την (γνωστή έως τότε στη βιβλιογραφία) πολυπλοκότητα της επίλυσης του προβλήματος εύρεσης της ισόνομης (egalitarian) και της “βέλτιστης” (optimal) λύσης. (7) Την διατύπωση του προβλήματος ΕΤ και την κωδικοποίησή του ως Πρόβλημα Ικανοποίησης Περιορισμών καθώς και την εφαρμογή της συνέπειας υπερακμής ως προ-επεξεργαστικό βήμα για την επίλυση παρομοίων προβλημάτων με τη χρήση πλατφόρμας Προγραμματισμού Περιορισμών. (8) Την επέκταση της έννοιας των περιστροφών με βάση συγκεκριμένους περιορισμούς στο πρόβλημα Ευσταθούς Εφοδιαστικής Αλυσίδας και στη χρησιμοποίησή τους για την αλγοριθμική αντιμετώπιση του προβλήματος.

Εκπόνηση Διδακτορικής Διατριβής

Παύλος Ειρηνάκης

Ε-mail: peir[at]aueb[dot]gr
Office phone: +30 2108203663
Fax: +30 2108203664
Address: Evelpidon 47-A & Lefkados 33 Room 907, GR-11362, Athens, Greece

Επίβλεψη

Δρ. Ιωάννης Μούρτος